[백준/Java] 7662번 이중 우선순위 큐

-Code

import java.io.*;
import java.util.*;

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

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

        for (int t = 0; t < testCase; t++) {
            // 이중 우선순위큐를 우선순위큐 2개로 하면 remove에 시간이 오래 걸림
            // 따라서 TreeMap을 통해 log(n)의 속도로 찾아서 해결
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            int commCnt = Integer.parseInt(br.readLine());

            for (int n = 0; n < commCnt; n++) {
                StringTokenizer st = new StringTokenizer(br.readLine());

                String comm = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                if (comm.equals("I")) {
                    treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
                } else {
                    // 비어있으면 넘어감
                    if (treeMap.isEmpty()) continue;
                    // 삭제일때 처리
                    int key;
                    if (num == 1) {
                        key = treeMap.lastKey();
                    } else {
                        key = treeMap.firstKey();
                    }
                    if (treeMap.get(key) == 1) {
                        treeMap.remove(key);
                    } else {
                        treeMap.put(key, treeMap.get(key) - 1);
                    }
                }
            }

            if (treeMap.isEmpty()) {
                System.out.println("EMPTY");
            } else {
                System.out.println(treeMap.lastKey() + " " + treeMap.firstKey());
            }
        }
    }
}

프로그래머스와 똑같은 문제가 있어서 우선순위 큐를 2개 이용을 하여 풀었더니 시간초과로 틀렸습니다. 찾아보니 프로그래머스는 테스트 케이스의 입력값의 범위가 작아서 가능했지만 백준은 그렇지 않아서 시간초과가 난 걸 알게 되었습니다. 그래서 무엇으로 해결하는지 모르다가 TreeMap를 알게 되었고 이를 사용하면 삭제, 최대, 최솟값 찾기의 속도가 log(n)의 속도이기 때문에 수가 적을 때는 손해를 보지만 수가 많아질 때 시간 이득을 보게 되어 이를 통해 해결했습니다.