백준 1927 최소 힙 - JAVA

1927 문제 링크

---

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

 

문제 설명

---

 

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    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> pqueue = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0 && pqueue.size() == 0) {
                sb.append(0).append("\n");
            } else if (x == 0 && pqueue.size() != 0) {
                sb.append(pqueue.poll()).append("\n");
            } else {
                pqueue.offer(x);
            }
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

 

 

알고리즘 설명

---

최소 힙은 완전 이진 트리 형태로 구성되며, 부모 노드는 자식 노드보다 항상 값이 작거나 같습니다. 문제를 풀다 보면 자료구조의 중요성을 더 잘 느낄 수 있습니다.

비록 우선순위 큐(Priority Queue)가 최소 힙을 자동으로 정렬해 주지만, 최소 힙의 작동 원리와 정렬 방법을 직접 이해하고 사용하는 것이 중요합니다.

우선순위 큐는 원소를 넣을 때마다 자동으로 최소값을 가장 앞에 배치해줍니다. 이를 활용하여 큐가 비어있다면 0을 출력하고, 비어있지 않다면 큐에서 가장 앞에 있는 원소를 제거하고 출력한 후, 그 값을 StringBuilder에 줄바꿈과 함께 추가하여 출력했습니다.

 

코드 해석

---

우선순위 큐를 생성하여 입력 되는 값이 0이고 pqueue가 비어있다면 0을 sb에 append, 입력되는 값이 0이고 pqueue가 비어있지 않다면 첫 번째 원소를 sb에 append, 입력되는 값이 0이 아니라면 해당 값을 pqueue에 추가했습니다.

이후, sb를 출력하였습니다.