문제 출처

단계별로 풀어보기 > 우선순위 큐 > 최소 힙
https://www.acmicpc.net/problem/1927

문제 설명

N개의 줄에 연산에 대한 정보를 나타내는 정수 x가 주어진다.
x가 자연수라면 배열에 x라는 값을 추가하는 연산,
x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거한다.
단, 배열이 비어 있는 경우에 0이 들어오면 0을 출력하면 된다.

접근 방법

PriorityQueue를 이용한다. 0이 들어오는 경우 가장 작은 수부터 PriorityQueue에서 추출하면 되므로 오름차순 기준으로 생성한다.
이후, 조건에 따라서 자연수 x가 0인 경우, 0일 때도 PriorityQueue가 비어있는 경우와 그렇지 않은경우
마지막으로 0이 아닌 자연수 x가 들어온 경우를 고려한다.

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

public class 최소_힙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

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

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++){
            int k = Integer.parseInt(br.readLine());

            if(k == 0){
                if(pq.size() == 0){
                    sb.append(0).append("\n");
                    continue;
                }
                sb.append(pq.poll()).append("\n");
            } else {
                pq.offer(k);
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

PriorityQueue은 이진트리 형태를 가지고 있따. 따라서 PriorityQueue의 시간복잡도를 고려하면
삽입의 경우 O(log n), 삭제의 경우에도 O(log n)이 걸리므로, 해당 코드의 시간 복잡도는 O(N log N)이다.

문제푼 흔적