[Boj_7662] 이중 우선순위 큐

📎 문제 링크

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

 

▸ 문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

▸ 입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 -231 이상 231 미만인 정수이다.

 

▸ 출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 4
• 🔔  문제 유형 : 자료 구조, 집합과 맵, 트리를 사용한 집합과 맵, 우선순위 큐
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

문제를 해결하기 위해 우선순위 큐(Priority Queue) 를 사용하는 이유는, 새로운 값이 들어올 때마다 정렬된 상태를 유지할 수 있기 때문이다. 이렇게 정렬된 데이터 구조를 이용하면 최댓값과 최솟값을 빠르게 찾을 수 있다.

단순히 remove() 메서드를 사용하여 큐 내부에서 원하는 원소를 제거하려 하면, 큐를 순차 탐색해야 하므로 O(n) 의 시간복잡도가 발생해 시간 초과가 난다. 따라서 더 효율적인 방식이 필요하다.

 

1️⃣ 최소힙, 최대힙과 Map 사용

탐색 속도를 개선하기 위해 최대 힙(Max Heap) 과 최소 힙(Min Heap), 두 개의 우선순위 큐를 동시에 사용한다.

• 최소 힙(Min Heap) : 완전 이진트리 구조이며, 루트 노드로 올라갈수록 값이 작아진다.
• 최대 힙(Max Heap) : 완전 이진트리 구조이며, 루트 노드로 올라갈수록 값이 커진다.

입력받은 정수를 두 힙에 동시에 저장해두면, 최댓값과 최솟값 탐색을 O(1) 에 처리할 수 있다.

 

하지만 여기서 같은 정수가 최대 힙과 최소 힙에서 서로 다른 위치에 저장되므로, 하나의 힙에서 삭제한 값이 다른 힙에도 여전히 남아 있을 수 있다.

이 문제를 해결하기 위해 Map을 함께 사용한다.

• Map에는 각 정수의 개수를 저장한다.
• 어떤 힙에서 원소를 꺼낼 때, Map을 확인하여 이미 다른 힙에서 소진된 값이라면 버리고 다시 꺼낸다.
• Map에서 개수가 0이 되면 해당 키를 제거한다.

이 과정을 통해 두 힙의 데이터 상태를 동기화할 수 있다.

 

🛠 delete 메서드

delete() 메서드는 힙에서 값을 꺼내고, 그 값이 유효한지 Map을 확인한 뒤 개수를 조정하는 역할을 한다.

• 힙에서 하나 꺼낸 후, Map에서 해당 값의 남은 개수를 확인한다.
• 이미 다른 힙에서 모두 소진된 값이라면 버리고(continue), 다시 꺼낸다.
• 유효한 값이라면 Map의 개수를 1 줄이거나, 0이 되면 키를 제거한다.

즉, delete() 메서드가 두 힙과 Map의 상태를 일치시켜 주기 때문에 최종적으로 올바른 최댓값, 최솟값을 얻을 수 있다.

 

 

---

 

이 문제는 TreeMap을 사용해서 해결할수도 있다.

 

💡 TreeMap 특징

TreeMap은 내부적으로 이진 탐색 트리(Red-Black Tree) 구조로 구현되어 있으며, 데이터를 삽입할 때 자동으로 정렬된 상태를 유지한다.

• 탐색, 삽입, 삭제 모두 O(log N) 의 시간 복잡도를 가진다.
• 따라서, PriorityQueue에서 발생하는 탐색 및 불일치 문제를 TreeMap 하나로 해결할 수 있다.

 

2️⃣ TreeMap 사용

기존 방식에서는 최소힙 + 최대힙 두 개의 우선순위 큐, 중복 개수 관리를 위한 Map, 이 세 가지를 동시에 사용해야 했다.

하지만  TreeMap은 정렬된 상태 유지 + Key-Value 관리를 동시에 제공하므로, 이를 하나로 통합할 수 있다.

• Key : 정수 값
• Value : 해당 정수의 개수 (중복 개수 관리)

이 문제에서 사용할 수 있는 TreeMap의 주요 메서드를 알아보자.

• firstKey() : 가장 작은 Key(최솟값) 반환
• lastKey() : 가장 큰 Key(최댓값) 반환
• map.put(key, value) : 정수를 삽입하거나 개수를 갱신
• map.remove(key) : 해당 Key의 개수가 0이 되면 제거

삭제 연산 시에는

• 최댓값(lastKey()) 또는 최솟값(firstKey())을 찾는다.
• 해당 Key의 개수를 1 줄인다.
• 개수가 0이 되면 remove()로 완전히 제거한다.

따라서, TreeMap을 사용하면 삽입/삭제/탐색을 모두 O(log N)에 처리할 수 있고, 코드가 간결해지며 최댓값과 최솟값을 바로 얻을 수 있어 구현이 훨씬 단순해진다.

 

위 풀이를 바탕으로 두 가지 방법에 대한 전체적인 코드를 각각 작성해 보면 아래와 같다.

 

✔ 코드

1️⃣ 최소힙, 최대힙과 Map 사용

메모리 : 444180KB
시간 : 2872ms

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

public class Main {
    static  Map<Integer, Integer> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (t --> 0) {
            int n = Integer.parseInt(br.readLine());

            PriorityQueue<Integer> min = new PriorityQueue<>();
            PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
            map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                char cmd = st.nextToken().charAt(0);
                int value = Integer.parseInt(st.nextToken());

                if (cmd == 'I') {
                    max.offer(value);
                    min.offer(value);

                    map.put(value, map.getOrDefault(value, 0)+1);
                } else { // D
                    if (map.size() == 0) continue;
                    else {
                        // 1 : 최댓값을 삭제, -1 : 최솟값을 삭제
                        if (value == 1) delete(max);
                        else delete(min);
                    }
                }
            }

            if (map.isEmpty()) sb.append("EMPTY").append('\n');
            else {
                int ans = delete(max);
                sb.append(ans).append(" ");
                if (map.size() > 0)  ans = delete(min);
                sb.append(ans).append("\n");
            }
        }

        System.out.println(sb.toString());

        br.close();
    }

    private static int delete(PriorityQueue<Integer> pq) {
        int num;
        while (true) {
            num = pq.poll();

            int cnt = map.getOrDefault(num, 0);

            if (cnt == 0) continue; // 이미 다른 큐에서 소진된 값이면 버리고 다시 뽑기

            if (cnt == 1) map.remove(num); // 남은 게 1개라면 아예 제거
            else map.put(num, cnt-1); // 2개 이상이면 개수만 줄임

            break;
        }

        return num;
    }
}

2️⃣ TreeMap 사용

메모리 : 439824KB
시간 : 2340ms

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 t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (t --> 0) {
            int n = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                char cmd = st.nextToken().charAt(0);
                int value = Integer.parseInt(st.nextToken());

                if (cmd == 'I') {
                    map.put(value, map.getOrDefault(value, 0)+1);
                } else { // D
                    if (map.size() == 0) continue;
                    else {
                        // 1 : 최댓값을 삭제, -1 : 최솟값을 삭제
                        int num = (value == 1) ? map.lastKey() : map.firstKey();
                        // num의 개수를 1 줄이고 (map.put(num, map.get(num) - 1))
                        // 갱신 전 값이 1이었는지 확인 (== 1)
                        if (map.put(num, map.get(num)-1) == 1) {
                            map.remove(num); // 개수가 0이면 아예 키를 제거
                        }
                    }
                }
            }

            if (map.isEmpty()) sb.append("EMPTY").append('\n');
            else sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
        }

        System.out.println(sb.toString());

        br.close();
    }
}

 

처음 우선순위 큐 + Map 방식으로 문제를 해결했을 때는, 두 자료구조를 동시에 관리해야 해서 다소 복잡했다. 이후 구글링을 통해 TreeMap으로도 해결할 수 있다는 것을 알게 되었고, 기존 방식의 기능을 TreeMap 하나로 통합할 수 있었다.
두 가지 방법으로 문제를 해결하면서, 트리 형태의 자료구조를 지닌 TreeMap이 메모리와 시간 측면에서도 더 효율적임을 확인할 수 있었다. 🤔💡