99클럽 코테 스터디 9일차 TIL

오늘의 학습 키워드

• 우선순위 큐 (Priority Queue)

문제

[백준 1927번 최소 힙 문제](https://www.acmicpc.net/problem/1927)

문제 이해

주어진 숫자들을 입력받아 최소 힙을 구현하고, 0이 입력으로 주어질 때마다 힙에서 가장 작은 값을 출력하는 문제입니다. 만약 힙이 비어 있을 경우 0을 출력합니다.

나의 풀이

package org.example.B\_1927;  

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

public class Main {  
    static int N;  
    public static void main(String\[\] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        N = Integer.parseInt(br.readLine());  
        StringBuilder sb = new StringBuilder();  
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();  

        for (int i = 0; i < N; i++) {  
            int num = Integer.parseInt(br.readLine());  
            if (num == 0) {  
                if (minHeap.isEmpty()) {  
                    sb.append(0).append("\\n");  
                } else {  
                    sb.append(minHeap.poll()).append("\\n");  
                }  
            } else {  
                minHeap.add(num);  
            }  
        }  
        System.out.println(sb);  
    }  
}  

풀이 설명

• 반복문을 통해 `N`개의 숫자를 입력받습니다.
• 입력된 숫자가 `0`일 경우:
  • 힙이 비어 있으면 `0`을 출력 결과에 추가합니다.
  • 힙이 비어 있지 않으면 `poll()` 메소드를 사용하여 힙에서 가장 작은 값을 출력 결과에 추가합니다.
• 입력된 숫자가 `0`이 아닐 경우:
  • 힙에 해당 숫자를 추가합니다.

오늘의 회고

• 우선순위 큐를 사용하여 최소 힙을 구현하는 문제를 해결함. 리스트를 사용해서 최소값을 구했으면 시간초과가 발생했을 것으로 예상됨.