[BOJ/] 백준 7662 - 이중 우선순위 큐 (Java)

7662 - 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

문제

이중 우선순위 큐(dual priority queue): 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조
/ 차이점: 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은/낮은 데이터 중 하나 삭제
데이터 삽입/삭제(우선순위 높은/낮은 것 삭제) 연산

입력
첫째 줄: 입력 데이터의 수를 나타내는 정수 T
각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수 나타내는 정수 k (k < 1,000,000)
k줄에는 연산을 나타내는 문자('D', 'I')와 정수 n 주어짐
I n: 정수 n을 Q에 삽입/ D -1: Q에서 최솟값 삭제/ D 1: Q에서 최댓값 삭제
최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨
출력
각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값 출력
(Q가 비어있다면 'EMPTY')

---

풀이

TreeMap

이진 탐색 트리 기반 Map/ key 정렬 유지(오름차순)

TreeMap<Integer, Integer> map = new TreeMap<>();

• 최댓값 삭제: `lastKey()`
• 최솟값 삭제: `firstKey()`

---

코드

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

// 이중 우선순위 큐
public class boj_7662 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        while (T-- > 0) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();

            for (int i = 0; i < k; i++) {
                String[] str = br.readLine().split(" ");
                String cmd = str[0];
                int num = Integer.parseInt(str[1]);

                if (cmd.equals("I")) {
                    map.put(num, map.getOrDefault(num, 0) + 1);
                } else {
                    if (map.isEmpty()) continue;

                    int key = (num == 1) ? map.lastKey() : map.firstKey();
                    if (map.get(key) == 1) map.remove(key);
                    else map.put(key, map.get(key) - 1);
                }
            }

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