BOJ_7662 : 이중 우선순위 큐

👉 문제링크

7662번: 이중 우선순위 큐

---

---

🔸 문제 분석 🔸

• int 범위의 값을 넣는 'I' 연산과 최대값 혹은 최소값을 빼는 'D'연산이 k번 수행된다.
  • 최종 연산 후 결과를 출력한다.
• k의 최대값이 1,000,000 이므로 값을 저장할 자료구조를 힙 형태로 구현해야 한다.
  • 힙정렬이 적용된, 우선순위 큐(Priority Queue) 혹은 TreeMap을 사용한다.

---

🔸 Priority Queue 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        // TestCase
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            // Input
            int k = Integer.parseInt(br.readLine());
            Queue<Integer> max_pq = new PriorityQueue<>(k, Collections.reverseOrder());
            Queue<Integer> min_pq = new PriorityQueue<>(k);
            Map<Integer, Integer> map = new HashMap<>();

            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                char order = st.nextToken().charAt(0);
                int num = Integer.parseInt(st.nextToken());
                // Orders
                if (order == 'I') { // Inque
                    max_pq.add(num);
                    min_pq.add(num);
                    map.put(num, map.getOrDefault(num, 0) + 1);
                } else {            // Deque
                    if (num == 1) {     // max_pq deque
                        deque(max_pq, map);
                    } else {            // min_pq deque
                        deque(min_pq, map);
                    }
                }
            }
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            boolean flag = true;

            for (int key : map.keySet()) {
                int num = map.get(key);
                if (num > 0) {
                    flag = false;
                    max = Math.max(max, key);
                    min = Math.min(min, key);
                }
            }

            if (flag) {
                sb.append("EMPTY").append('\n');
            } else {
                sb.append(max).append(' ').append(min).append('\n');
            }
        }
        System.out.print(sb);
    }

    private static void deque(Queue<Integer> queue, Map<Integer, Integer> map) {
        while (!queue.isEmpty()) {
            int num = queue.poll();

            if (map.get(num) > 0) {
                map.put(num, map.get(num) - 1);
                break;
            }
        }
    }
}

🔸 코드 해석 🔸

• 우선순위 큐를 2개 만들어 각각 최대힙과 최소힙으로 정렬조건을 지정해 최대값과 최소값을 빠르게 구할 수 있도록 한다.
• 현재 유효한 원소를 추적하기 위해 map으로 공통 원소를 관리한다.
  • 우선순위 큐에서 poll한 값이 map에 있는 원소라면, 유효하므로 D연산이 수행 된 것이다.
  • 우선순위 큐에서 poll한 값이 map에 없는 원소라면, 유효하지 않으므로 다시 한 번 poll한다.

---

🔸 Priority Queue 🔸

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        // TestCase
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            // Input
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();

            int max, min;
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                char order = st.nextToken().charAt(0);
                int num = Integer.parseInt(st.nextToken());
                // Orders
                if (order == 'I') { // Inque
                    treeMap.put(num, treeMap.getOrDefault(num,0)+1);
                } else {            // Deque
                    if (treeMap.isEmpty()) continue;
                    if (num == 1) {     // max deque
                        max = treeMap.lastEntry().getValue();
                        if (max == 1) {
                            treeMap.remove(treeMap.lastKey());
                        } else {
                            treeMap.put(treeMap.lastKey(), max-1);
                        }
                    } else {            // min deque
                        min = treeMap.firstEntry().getValue();
                        if (min == 1) {
                            treeMap.remove(treeMap.firstKey());
                        } else {
                            treeMap.put(treeMap.firstKey(), min-1);
                        }
                    }
                }
            }

            if (treeMap.isEmpty()) {
                sb.append("EMPTY").append('\n');
            } else {
                sb.append(treeMap.lastKey()).append(' ').append(treeMap.firstKey()).append('\n');
            }
        }
        System.out.print(sb);
    }
}

🔸 코드 해석 🔸

• TreeMap을 만들어 원소를 저장한다.
  • java의 TreeMap은 Red-Black Tree로, 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값의 형태를 유지한다.
  • key를 자동으로 정렬해주기 때문에 'I'연산으로 넣는 값을 키로 넣고, 그 누적 값을 value로 저장한다. (중복된 값도 'I' 연산으로 들어오기 때문)
  • firstKey로 최소값, lastKey로 최대값에 접근할 수 있다.

---

🔸 end 🔸

• 이중 우선순위 큐를 구현하는 방법이 떠오르지 않아서 고민하다 풀이를 찾아보았다.
  • 처음 풀이는 우선순위 큐 2개와 맵 1개를 이용한 풀이었다.
    • 최대힙과 최소힙을 어떻게 함께 구현할까 고민했는데 이 풀이가 딱이라고 생각했다.
  • 좀더 간결한 풀이가 없을까 했는데 TreeMap 풀이가 더 정석적인 것 같다.
    • 코드도 짧아지고 시간복잡도도 낮아졌다.
• 문제 분석과 풀이 계획을 적으며 풀이했다.