문제 📕

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

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
   프로그램은 처음에 비어있는 배열에서 시작하게 된다.

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

접근 방법 🧐

우선순위 큐 Priority Queue

• 일반 Queue는 FIFO 이다. (First In First Out)
• Priority Queue는 "내부에서 우선순위 정한다" 자동으로!!

큐는 써봤지만 Priority Queue는 처음 써본다. 뭔가 BigInteger 처음 봤을 때 느낌이랄까 🙄
https://www.acmicpc.net/problem/1271 (백준 BigInteger문제.. long 썼는데 런타임 에러떴을때 당황스러웠다)

1. 입력값인 num이 0이면 출력
   • 비어있으면 '0' 출력
   • 아니면 들어있는 값 poll 하기
2. 입력값인 num 이 0이 아니면 add 하기

내가 쓴 코드 ✍️

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

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));
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		int N = Integer.parseInt(br.readLine());
		for(int i=0;i<N;i++) {
			int num = Integer.parseInt(br.readLine());
			if(num == 0) {
				if(pq.isEmpty()) {
					bw.write("0\n");					
				}
				else {
					bw.write(pq.poll()+"\n");
				}
			}
			else {
				pq.add(num);
			}
		}
		bw.flush();
		bw.close();
	}
}

느낀점 📖

우선순위 큐에대한 개념만 알면 쉽게 풀 수 있는 문제였다. 솔직히 실버2까지는 아닌 것 같다...? 아마도..?