[실버 2] [Java] 백준 11279번: 최대 힙

아이디어

최대 힙 문제이다. 

우선순위 큐, 그 중 최대 힙은

부모 노드가 항상 자식보다 큰 완전 이진 트리이다.

 

새로운 노드를 넣을 때, 가장 마지막 노드에 넣고, 힙의 조건(부모 >= 자식)을 만족할 때까지 교환한다.

삭제할 때에는 root를 꺼내고, 마지막 노드를 root로 올린 뒤 힙의 조건을 만족할 때까지 교환한다.

 

이를 코드로 구현하면 다음과 같다.

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

public class N11279 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int input  = Integer.parseInt(br.readLine());
        int N = input;
        PriorityQueue<Integer> maxHaep = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 1; i <= N; i++) {
            input =  Integer.parseInt(br.readLine());
            if (input == 0) {
                if (maxHaep.isEmpty()) {
                    bw.write(0 + "\n");
                } else {
                    bw.write(maxHaep.poll() + "\n");
                }
            } else {
                maxHaep.add(input);
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.