[백준 / 골드4] 7662 이중 우선순위 큐 (Java)

문제 보기

사용한 것

• 우선순위 큐

풀이 방법

• 우선순위 큐를 최소, 최대 2개 생성한다.
• Map을 사용하여 두 우선순위 큐의 싱크를 맞춘다.
• 동기화에는 remove()가 사용되며 우선순위 원소 중 처음으로 존재하는 값이 나올 때까지 허수를 삭제한다.
• iCt와 dCt로 현재 원소 개수를 판별한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int k = Integer.parseInt(br.readLine());
            PriorityQueue<Integer> minPQ = new PriorityQueue<>();
            PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
            Map<Integer, Integer> map = new HashMap<>();
            int iCt = 0;
            int dCt = 0;

            for (int j = 0; j < k; j++) {
                String[] line = br.readLine().split(" ");
                char command = line[0].charAt(0);
                int num = Integer.parseInt(line[1]);

                if (command == 'I') {
                    minPQ.offer(num);
                    maxPQ.offer(num);
                    map.put(num, map.getOrDefault(num, 0) + 1);
                    iCt++;
                } else if (iCt > dCt) {
                    int removed = remove(num == -1 ? minPQ : maxPQ, map);
                    map.put(removed, map.get(removed) - 1);
                    dCt++;
                }
            }

            if (iCt == dCt) {
                System.out.println("EMPTY");
            } else {
                minPQ.offer(remove(minPQ, map));
                maxPQ.offer(remove(maxPQ, map));
                System.out.println(maxPQ.poll() + " " + minPQ.poll());
            }
        }
    }

    public static int remove(PriorityQueue<Integer> pq, Map<Integer, Integer> map) {
        int removed;
        do {
            removed = pq.poll();
        } while (pq.size() > 0 && map.get(removed) == 0);

        return removed;
    }
}