[백준, JAVA] 1927번 : 최소 힙

1. 문제

2. 아이디어

• 우선순위 큐를 활용한다

2-1 우선순위 큐

• 큐(Queue)는 First in-First Out 구조로, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조이다. 유통기한에 민감한 우유 판매와 같은 형태.

• 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

3. 코드

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

public class BOJ_2_1927 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(); // 낮은 숫자가 우선순위 높은게 기본 기준
        
        for (int i = 0; i < N; i++) {
           int x = Integer.parseInt(br.readLine());
           
            if (x>0) { // x가 자연수면 배열에 추가하는 연산
                minQueue.offer(x);
            } else { // x가 0인데 배열이 비어있으면 0 출력
                if (minQueue.isEmpty()) {
                	System.out.println(0);                    
                }
                else{ // x가 0이면 배열 값 중에 최솟값 출력
                	System.out.println(minQueue.poll());
                }
            }
        }
        
	}
}

4. 느낀점

• 우선순위 큐의 기본 설정 값이 최솟값이므로, 별도의 Comparator 설정이 없어도 풀 수 있었다.

• 해당 시리즈의 최대 힙 등의 문제를 풀기 위해서는 우선순위 기준에 대해 별도 설정이 필요하겠다.