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

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

7662번: 이중 우선순위 큐

처음에는 PriorityQueue를 이용해서 min-heap, max-heap을 구현하는 방법으로 문제를 풀려고 했지만

구현하는게 쉽지 않아 결국 정답을 본 문제이다.

정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            int N = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for (int j = 0; j < N; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String cmd = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                if (cmd.equals("I")) {
                    map.put(num, map.getOrDefault(num, 0) + 1);
                    continue;
                }
                if (map.isEmpty()) {
                    continue;
                }
                // TreeMap이 제공하는 firstKey()와 lastKey() 이용
                int n = (num == 1) ? map.lastKey() : map.firstKey();
                // 해당 정수의 개수를 -1 해주면서 만약 0개가 된다면 삭제
                if (map.put(n, map.get(n) - 1) == 1) {  
                    map.remove(n);
                }


            }
            if (map.size() == 0) {
                sb.append("EMPTY\n");
                continue;
            }
            sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
        }
        System.out.println(sb.toString());
    }
}

시나리오

1. 레드-블랙 트리를 기반으로 구현된 TreeMap을 사용하여 오름차순(키 값 기준) 정렬을 유지한다.
2. 그리고 TreeMap 요소 중 최솟값은 map.firstKey(), 최댓값은 map.lastKey()로 탐색한다.(이 때 Map타입이 아닌 TreeMap타입으로 받아야 위 메서드를 사용할 수 있다.)
3. 중복된 숫자는 TreeMap의 value값에 카운팅한다.
4. 문자 I가 입력되면 같이 입력된 숫자에 해당하는 value가 있을 땐 +1, 아닐 땐 1을 put한다.
5. 문자 D가 입력되면 TreeMap이 비었을 땐 conitnue, 그렇지 않을 땐 현재 value의 -1을 put한다. 다만, value가 1이라면 해당 요소를 아예 remove한다.
6. 한 테스트케이스를 전부 돌았을 때 TreeMap의 size가 0이면 EMPTY를 그 이상이라면 최댓값과 최소값을 순서대로 StringBuilder에 append
7. 모든 TC를 다 돌았을 때 출력한다.

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeMap.html

TreeMap (Java SE 17 & JDK 17)

-------------

새로운 풀이(2024.3.14)

시나리오

treeSet을 생성해 매 입력을 처리한다. 단, treeSet은 중복요소를 가질 수 없으므로, Integer타입이 아닌 객체 타입의 요소를 갖도록 만들고 해당 객체에는 value라는 필드를 만든 뒤 Comparable을 구현한다. 그리고 treeSet은 compareTo가 0을 반환하는 경우에도 중복요소로 인식하기 때문에 비교 대상인 두 요소가 같을 때, compareTo가 음수또는 양수를 반환하도록 로직을 짠다.

위 두 풀이를 비교해봤을 때 TreeMap은 중복된 요소가 생기면 value+1을 하면 되므로 TreeMap을 사용한 풀이가 훨씬 간단해보인다. heap자료구조가 필요하되 중복된 요소를 처리하고자 한다면 TreeMap의 사용도 떠올려보자.