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

---

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

---

📌 문제

문제 유형

• 자료 구조

문제 설명

입력

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

출력

EMPTY
333 -45

🔍 문제 풀이

자바의 PriorityQueue는 최소 힙만 지원하기 때문에, 최대값을 함께 관리하려면 굉장히 복잡하다.

TreeMap<Integer, Integer>를 사용하면 자동 정렬 기능과 함께 중복 값도 개수로 관리할 수 있어,
이중 우선순위 큐를 훨씬 쉽고 간단하게 구현할 수 있다.

🌳 TreeMap이란?

• TreeMap은 key를 자동 정렬해주는 Map 자료구조이다.
• 내부적으로 Red-Black Tree(이진 탐색 트리) 기반으로 구현되어 있다.
• key 중복은 허용되지 않으므로, value에 개수를 저장해 중복을 관리한다.
• firstKey()와 lastKey()를 통해 최솟값과 최댓값을 O(log N)에 가져올 수 있다.

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

map.put(5, 1);
map.put(2, 1);
map.put(7, 1);

System.out.println(map.firstKey()); // 2 (최솟값)
System.out.println(map.lastKey());  // 7 (최댓값)

key 중복은 허용하지 않으므로, 중복값은 다음처럼 value로 개수를 관리한다.

map.put(5, map.getOrDefault(5, 0) + 1); // 5가 없으면 0, 있으면 기존 개수 +1

삭제 처리도 value로 개수를 관리한다.

int count = map.get(5);
if (count == 1) map.remove(5);
else map.put(5, count - 1);

📌 놓친 점

처음에는 TreeMap이 있는줄 모르고 PriorityQueue로 풀려고 했다가, 도저히 풀리지가 않았다.

그러다가 검색을 통해 정렬과 중복 카운팅을 동시에 처리할 수 있다는 TreeMap이라는 자료 구조를 알게 되었다.

💻 전체 코드

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

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());
        while(t --> 0){
            TreeMap<Integer, Integer> map = new TreeMap<>();

            int k = Integer.parseInt(br.readLine());
            while (k-- > 0) {

                StringTokenizer st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

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


                    // 삭제할 대상 key 선택 (삭제는 아직 하지 않음)
                    int key=0;
                    if (n == 1) {
                        key = map.lastKey();  // 최댓값 key 가져오기
                    } else {
                        key = map.firstKey(); // 최솟값 key 가져오기
                    }

                    // 삭제
                    int count = map.get(key);
                    if (count == 1) {
                        map.remove(key); // 개수가 1개 -> key 자체 삭제
                    } else {
                        map.put(key, count - 1);  // 개수가 여러 개 -> value만 1 감소
                    }
                }
            }
            if (map.isEmpty()) {
                System.out.println("EMPTY");
            } else {
                System.out.println(map.lastKey() + " " + map.firstKey());
            }
        }
    }
}