[Java] BOJ 1927 최소 힙

문제 

문제 링크 https://www.acmicpc.net/problem/1927

• 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
  1. 배열에 자연수 x를 넣는다.
  2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
• 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
• 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
• 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
• 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
• x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
• 입력에서 0이 주어진 횟수만큼 답을 출력한다.
• 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

아이디어

• 최소 힙 문제가 PriorityQueue를 설명하고 있다고 생각했다.
• Priority Queue가 우선순위 큐로, 우선순위가 가장 낮은 값이 먼저 나오게 되어있는데, 이 문제에서 Integer를 넣었을 때 숫자가 작을 수록 우선순위가 낮다고 판단되어 위로 올라간다.
• 따라서 맨 위의 값이 최솟값이 된다고 할 수 있다.
• 따라서 0이 들어왔을때 PriorityQueue가 비어있다면 0을 출력하게하고 비어있지 않다면 PriorityQueue의 맨 위 값을 출력한다.
• 그리고 다른 숫자가 들어오면 PriorityQueue에 넣는다.

겪은 시행착오

• X

나름 이문제는 PriorityQueue라는 개념을 알고 있다면 쉽게 풀 수 있는 문제였다!

코드

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

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

        // 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최솟값이 됨
        // Primary Queue는 우선순위 큐로 우선순위가 가장 낮은 값이 먼저 나오게 되어있음
        // 우선순위가 낮다는 것은 Integer를 넣었을 때, 최솟값으로 판단됨
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 연산의 개수
        int N = Integer.parseInt(br.readLine());

        // 연산의 개수만큼 반복
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(br.readLine());

            // 만약 입력받은 수가 0일때
            if(x == 0){
                // minHeap이 비어있다면
                if(minHeap.isEmpty()){
                    // 0을 출력
                   sb.append(0 + "\n");
                }
                // 만약 minHeap이 비어있지 않다면
                else{
                    // minHeap의 꼭대기 값을 출력하고
                    sb.append(minHeap.peek() + "\n");

                    // minHeap의 맨 위의 값을 제거
                    minHeap.poll();
                }
            }
            // 만약 입력받은 수가 0이 아니라면
            else{
                // minHeap에 x를 추가
                minHeap.add(x);
            }
        }

        System.out.println(sb);
    }
}