[SW Expert Academy] 2930 힙 [Java]

[ 시간복잡도 ]

[ 핵심풀이 ]

Collections의 PriortyQueue를 잘 사용할 수 있느냐 묻는 문제이기도 했다.

PriorityQueue의 경우 Default가 가장 작은수가 맨 위에 오게되므로

Collections.reverseOrder()을 사용하여 가장 큰 수가 맨 위에 오도록 해야한다.

[ 핵심소스 ]

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

[ Java ]

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class _2930_힙 {
    static void init() {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            int dolist = sc.nextInt();
            System.out.print("#" + t + " ");
            solve(dolist, sc);
            System.out.println();
        }
    }

    static void solve(int dolist, Scanner sc) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());

        for (int d = 0; d < dolist; d++) {
            int type = sc.nextInt();
            switch (type) {
            case 1:
                int value = sc.nextInt();
                q.add(value);
                break;
            case 2:
                int output;
                if (q.isEmpty())
                    output = -1;
                else
                    output = q.poll();
                System.out.print(output + " ");
                break;
            }
        }
    }
    public static void main(String[] args) {
        init();
    }
}