[Java] 백준(실버-2) 1927번 - 최소 힙

문제 풀이

---

이 문제는 주어진대로 최소 힙을 우선순위 큐를 이용해 구현하면 되는 간단한 문제이다.

아이디어 도출

이 문제에서 요구하는 최소 힙을 어떻게 우선순위 큐로 구현할 수 있는 걸까?

일반적인 큐(Queue)는 FIFO(First in - First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 구조이다. 그런데 우선순위 큐(Priority Queue)는 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조로 이루여져있다.

우선순위 큐인 PriorityQueue를 선언할 때, 인자로 Comparator 클래스를 넣어서 우선순위의 기준을 설정할수 있다. 다만 이번 문제에서는 기본값인 최소 힙을 구현하기에 별도의 Comparator 설정 없이 풀 수 있다.

따라서 이러한 우선순위 큐를 이용하면 쉽게 최소 힙을 구현할 수 있다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

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));

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

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

        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            
            // 만약 입력값이 0보다 큰 자연수라면 우선순위 큐에 삽입.
            if(num > 0) {
                q.offer(num);
                continue;
            }

            // 0일 때 우선순위 큐가 비어있다면 0을, 비어있지 않다면 가장 작은 수를 꺼낸다.
            if(!q.isEmpty()) {
                bw.write(q.poll()+"\n");
            } else {
                bw.write("0"+"\n");
            }
            
        }
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.