[BOJ] 1927 최소 힙 - Java

[문제]

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

[문제 풀이]

우선순위 큐는 힙으로 구현되면 위 문제는 우선순위 큐로 규현해야 하는 문제이다.

자바에서 우선순위 큐는 PriorityQueue로 구현 할 수 있다.

기본으로 최소힙으로 구현되어 있기 때문에 문제에서 0이 입력 받을 때마다 queue가 비어 있지 않다면 그냥 출력해 주면 되는 문제이다.

 

[코드]

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

public class Main {

    static int N;
    static PriorityQueue<Integer> queue = new PriorityQueue<>();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = stoi(br.readLine());

        for (int i=0; i<N; i++) {
            int x = stoi(br.readLine());

            if (x==0) {
                if (queue.isEmpty()) sb.append(0).append("\n");
                else {
                    sb.append(queue.poll()).append("\n");
                }
            } else {
                queue.offer(x);
            }
        }

        System.out.println(sb);
    }
}

[실행 결과]

실행 결과는 위와 같다.