99클럽 코테 스터디 19일차 TIL - 백준 최소힙

백준 - 최소 힙

기술 : 최소힙

해결방안 : 우선순위큐를 사용해서 문제를 풀면 되는 문제.

PriorityQueue<Integer> queue = new PriorityQueue<>()를 사용하면 해결되는 문제.

PriorityQueue란?
PriorityQueue는 Java의 컬렉션 프레임워크 중 하나로, 우선순위에 따라 요소를 정렬하는 큐입니다.
요소는 기본적으로 자연 순서 또는 제공된 Comparator에 따라 정렬됩니다.
자연 순서: Integer의 경우, 오름차순(작은 값 → 큰 값)으로 정렬됩니다.
사용자 정의 순서: Comparator를 사용하여 정렬 기준을 커스터마이징할 수 있습니다.
FIFO(First-In-First-Out)가 아닌, 최우선 순위를 가진 요소가 먼저 나오는 자료 구조입니다.

최대힙을 구하려면 PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                if (!queue.isEmpty()) {
                   sb.append(queue.poll()+"\n");
                } else {
                    sb.append("0\n");
                }
            } else {
                queue.add(x);
            }
        }
        System.out.println(sb);
    }
}