[백준] 7662번. 이중 우선순위 큐(JAVA)

문제

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

---

풀이(20분)

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));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());
                char command = st.nextToken().charAt(0);
                int num = Integer.parseInt(st.nextToken());

                if (command == '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());
            }
        }
    }
}

---

문제 풀이 전략

 

처음엔 asc 우선순위 큐와 desc 우선순위 큐 두 개를 만들어 풀이를 해볼 생각이었다.

하지만 size를 가지고 관리를 하려고 해도, 값이 실제 큐에서 삭제되지 않는다면 정렬 상 문제가 발생할 수 있었다.

 

따라서, 정렬을 보장해주고 value를 통해 중복된 값의 개수를 컨트롤할 수 있는 TreeMap 자료구조를 선택하여 해결하였다.