백준 11729번 : 최대 힙 [Java]

문제 링크

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

문제 설명

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int x = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < x; i++) {
           int num = Integer.parseInt(br.readLine());

           if (num == 0) {
                if (pq.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(pq.poll());
                }
           } else {
               pq.offer(num);
           }
        }
        System.out.println();
    }
}

풀이

1. 변수 X에 연산의 갯수를 받아서 X에 횟수 만큼의 값을 출력한다.

2. 힙 관련 문제를 구현 시에는 PriorityQueue를 사용한다. -> 기본 Default(최소 힙)

3. 최대 힙 구현을 위해 우선순위 큐 선언 시에 Comparator.reverseOrder() 사용하여 내림차순 정렬을 한다.

4. 값이 입력될 때마다 0일 때 pq에 값이 없으면 '0'을 출력하고, 그 외의 경우에는 값을 제거하여 출력한다.

5. 값이 0이 아닌 경우에는 pq에 값을 넣는다.