[BOJ] 11279 최대 힙 - Java

[문제]

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

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

[문제 풀이]

이 문제는 이전 최소 힙 문제 풀이와 유사하다.

PriorityQueue에 넣을 때 -1을 곱해서 넣어주고

뺄 때 다시 -1을 곱한 값을 출력해 주면 된다.

참고: https://dos-soles.tistory.com/11?category=873473

 

[코드]

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

public class Main {

    static int N;
    static PriorityQueue<Integer> queue = new PriorityQueue<>();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        N = stoi(br.readLine());
        for (int i=0; i<N; i++) {
            int x = stoi(br.readLine());

            if (x == 0) {
                if (queue.isEmpty()) sb.append(0).append("\n");
                else {
                    sb.append(queue.poll()*-1).append("\n");
                }
            } else {
                queue.offer(x*-1);
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]

실행 결과는 위와 같다.