[우선순위 큐] 백준 1927번 최소 힙(Java)

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

1927번: 최소 힙

📚 문제

최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

입력에서 0이 주어진 회수만큼 답을 출력한다.

만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1	예제 출력 1
9 0 12345678 1 2 0 0 0 0 32	0 1 2 12345678 0

 

📝 문제 해결

우선순위 큐는 자바에서 기본적으로 오름차순으로 정렬되므로 입력받은 정수가

• 자연수라면 우선순위 큐에  넣어주고 (offer)
• 0일 경우 그 값을 우선순위 큐의 가장 첫번째 원소를 출력하고 제거해준다. (poll)

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class BOJ1927 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                if (queue.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(queue.poll());
                }
            } else {
                queue.offer(n);
            }
        }
    }
}