이중 우선순위 큐

풀이

이 문제를 딱 보자마자 정렬 기준이 다른 우선순위 큐를 이용해서 풀면 될 것이라고 생각했습니다. 하나는 최대힙, 하나는 최소힙으로 하고 숫자를 넣을 때마다 size를 1 올리고 뺄 때마다 size를 1 빼면 두 개의 힙에 몇 개가 남든지 size로 판단하고 size가 0보다 큰데 힙 둘 중 하나가 비어있을 수 없기 때문에 이 방식으로 풀면 풀릴 거라 생각하고 코드를 짰습니다.

import java.util.*;


public class Main {


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();
        while (tc-- > 0) {
            int k = scanner.nextInt();
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            PriorityQueue<Integer> reversePq = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            int size = 0;
            for (int i = 0; i < k; i++) {
                String command = scanner.next();

                if (command.equals("I")) {
                    int num = scanner.nextInt();
                    pq.offer(num);
                    reversePq.offer(num);
                    size++;
                } else {
                    int direction = scanner.nextInt();
                    if (size <= 0) continue;
                    if (direction == 1) {
                        reversePq.poll();
                    } else {
                        pq.poll();
                    }
                    size--;
                }
            }

            if (size <= 0) System.out.println("EMPTY");
            else System.out.println(reversePq.poll() + " " + pq.poll());
        }
    }
}

숫자를 넣을 때는 $O(\log N)$시간이 걸리고 뺄땐 $O(1)$ 시간이 걸리므로 시간초과는 뜨지 않지만 실패했습니다. 이유는 전혀 모르겠습니다. 아마 size문제인 것 같은데 시간이 너무 오래걸려서 다른 방식을 생각했습니다.
바로 트리맵을 이용하는 것입니다. 이진 탐색 트리를 이용해서 풀기로 했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for (int i = 0; i < k; i++) {
                String[] command = br.readLine().split(" ");
                if (command[0].equals("I")) {
                    map.put(Integer.parseInt(command[1]), map.getOrDefault(Integer.parseInt(command[1]), 0) + 1);
                } else {
                    if (map.size() == 0) continue;
                    if (Integer.parseInt(command[1]) == 1) {
                        if (map.get(map.lastKey()) > 1) map.put(map.lastKey(), map.get(map.lastKey()) - 1);
                        else map.remove(map.lastKey());
                    } else {
                        if (map.get(map.firstKey()) > 1) map.put(map.firstKey(), map.get(map.firstKey()) - 1);
                        else map.remove(map.firstKey());
                    }
                }
            }
            if (map.size() == 0) System.out.println("EMPTY");
            else System.out.println(map.lastKey() + " " + map.firstKey());
        }
        br.close();
    }
}

이것 또한 숫자를 넣을 때와 뺄 때의 시간 복잡도가 $O(\log N)$이므로 충분히 시간 내에 해결할 수 있습니다. $1000000 \times \log_2 1000000$는 약 $20000000$이므로 충분히 가능합니다.

회고

우선순위 큐로 푸는 방식이 왜 틀렸는지 모르겠습니다.