[Java] baekjoon_1927 : 최소 힙

자료 구조, 우선순위 큐

최소 힙 : Silver2

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

 

풀이

import java.io.*;
import java.util.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < N; i++) {
      int num = Integer.parseInt(br.readLine());
      if (num > 0) {
        pq.offer(num);
      } else if (num == 0) {
        if (pq.isEmpty()) {
          bw.write("0\n");
        } else {
          bw.write(pq.poll() + "\n");
        }
      }
    }

    bw.flush();
    br.close();
    bw.close();
  }
}

 

ㄴ pq.offer(num)는 우선순위 큐에 정수 num을 추가하는 것입이다.

    ㄴ offer() 메서드는 우선순위 큐에 요소를 추가하는 메서드로, 추가된 요소는 우선순위 큐 내부적으로 정렬되어 위치가 결정된다.
ㄴ 또한, pq.poll()는 우선순위 큐에서 가장 작은 값을 꺼내는 것이다.

    ㄴ poll() 메서드는 우선순위 큐에서 요소를 제거하고 해당 요소를 반환하는 메서드이다.

    ㄴ 따라서 이 코드에서는 0이 입력되면 우선순위 큐에서 가장 작은 값을 꺼내어 출력하는 역할을 한다.

 

우선순위 큐 (Priority Queue)

PriorityQueue<Integer> pq = new PriorityQueue<>();

 

우선순위 큐(Priority Queue)는 큐(Queue) 자료구조의 한 종류로, 각 요소마다 우선순위를 가지고 있다.

일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조이다.
하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다.

 

PriorityQueue 클래스는 기본적으로 작은 값이 우선순위가 높은 방식으로 동작하며, 정수형의 경우 오름차순으로 정렬된다.

또한, 우선 순위 큐는 우선순위가 높은 요소가 먼저 꺼내지는 특징을 가지고 있다.

 

우선순위 큐는 요소를 추가할 때마다 내부적으로 요소들을 우선순위에 따라 정렬하고, 가장 우선순위가 높은 요소가 큐의 맨 앞에 위치하게 됩니다.

정수형 값을 저장하는 우선순위 큐를 선언할 경우, 정수형 값들을 추가할 때마다 우선순위에 따라 자동으로 정렬되어 관리된다.

이러한 우선순위 큐는 일반적으로 이진 힙(Binary Heap)을 기반으로 구현된다.

힙은 부모 노드가 자식 노드보다 작은(또는 큰) 값을 가지는 이진 트리로, 우선순위 큐의 경우에는 작은 값을 가지는 경우가 일반적이다.