문제 출처

단계별로 풀어보기 > 우선순위 큐 > 최대 힙
https://www.acmicpc.net/problem/11279

문제 설명

N개의 수가 주어질 때, 각각 정수 x가 자연수이면 배열에 x 값을 추가하고, x가 0이면 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

접근 방법

java의 PriorityQueue를 이용하여 내림차순으로 우선순위를 정하여 조건에 따라서 해당 값을 출력하고 배열에서 제거한다.

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

public class 최대_힙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i<N; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(pq.size() == 0){
                    bw.write(0 + "\n");
                    continue;
                }
                bw.write(pq.poll() + "\n");
            }else{
                pq.add(x);
            }
        }

        bw.flush();
        bw.close();
        br.close();

    }
}

Review

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

public class 최대_힙_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++){
            int x = Integer.parseInt(br.readLine());

            if(x == 0){
                if(pq.isEmpty()){
                    sb.append(0).append("\n");
                    continue;
                }
                sb.append(pq.poll()).append("\n");
            } else {
                pq.offer(x);
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

오랜만에 우선순위 큐를 다뤄봤는데, 내림차순은 Collections.reverseOrder()를 이용하여 내림차순을 만드는 것을 까먹었었다.

Review
N개를 우선순위 큐에 삽입 및 삭제를 하는 과정이 포함되어있으므로, 삽입은 O(log n)의 시간 복잡도를 삭제는 O(1)이므로 O(Nlog N)의 시간복잡도를 가진다.

추가로 Size 조회는 O(1)의 시간 복잡도를 가진다.

문제푼 흔적

Review