BOJ11279 최대 힙

https://www.acmicpc.net/problem/11279 (opens new window)

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원도록 한다.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

PriorityQueue

Java에서 PriorityQueue는 기본적으로 최소힙으로 구현되어 있다. 그렇기 때문에 값을 poll 할 경우 우선순위 오름차순을 기준으로 값을 꺼내온다.

그렇기 때문에 내부적으로 우선순위 내림차순으로 꺼내올 수 있도록 해야 한다.

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

제출 코드

아래는 최종 제출 코드이다.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ11279 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

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

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            if (x == 0 && !priorityQueue.isEmpty()) {
                stringBuilder.append(priorityQueue.poll()).append("\n");
            } else if (x == 0) {
                stringBuilder.append("0\n");
            } else {
                priorityQueue.add(x);
            }
        }

        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #자료 구조 #우선순위 큐