[실버 2] [Java] 백준 1927번: 최소 힙

아이디어

이 문제는 우선순위 큐를 이용하는 문제이다. 우선순위 큐는 최소 힙으로 이루어진 자료구조이다.

힙(Heap)은 완전이진트리 기반의 자료구조로, 각 노드의 값이 규칙에 따라 부모-자식의 관계를 가지는 트리이다.

최소 힙이면 부모가 자식의 이하 값이 된다.

 

자바에서는 이를 PriorityQueue로 구현해둬서, 쉽게 이를 구현할 수 있다.

 

이를 코드로 구현하면 다음과 같다.

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

public class N1927 {
    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<>();

        for (int i = 1; i <= N; i++) {
            int x =  Integer.parseInt(br.readLine());
            if (x == 0) {
                if (pq.isEmpty()) {
                    bw.write(0 + "\n");
                } else {
                    bw.write(pq.poll() + "\n");
                }
            } else {
                pq.add(x);
            }
        }
        bw.flush();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.