[백준] 11279번: 최대 힙 - JAVA

🔗 문제 링크

BOJ 11279번: 최대 힙

11279번: 최대 힙

 

📝 풀이 과정

힙을 직접 구현해도 좋겠지만, Java에 있는 PriorityQueue를 사용해 문제를 해결하기로 했다.(List로 문제를 풀 수도 있지만, n개의 숫자를 출력할 때마다 정렬하면 $O(n^2\log n)$으로 시간초과 발생)

PriorityQueue는 add와 poll 모두 O(log n)으로 $O(n\log n)$만에 문제를 해결할 수 있다.

PriorityQueue는 기본적으로 오름차순 정렬이기 때문에, Collections.reverseOrder()를 활용해 내림차순으로 변경해준다. 출력을 할 때, queue의 size = 0이라면 배열이 비어있는 경우이므로, 0을 출력해준다.

 

💡 문제에서 범위가 연산의 개수가 최대 100,000개이다. 이럴 경우 Scanner는 느리기 때문에 BufferedReader를 활용해보자!

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
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> que = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num == 0)
                sb.append(que.size() == 0 ? 0 : que.poll()).append('\n');
            else que.add(num);
        }
        System.out.println(sb.toString());
    }
}

📊 제출 결과