백준 7662 이중 우선순위 큐 Java: TreeMap으로 중복값까지 관리하기

백준 7662번 원문에는 한 달 만에 다시 풀었고, 문제를 붙잡은 시간은 사실상 하루 꼬박이었다고 적혀 있다. 가장 오래 막힌 이유도 분명했다. 문제 이름이 ‘이중 우선순위 큐’라서 최소 힙과 최대 힙만으로 끝내려 했지만, 두 자료구조에서 삭제된 원소를 동기화해야 했다.

• 백준 7662번 이중 우선순위 큐

두 힙과 지연 삭제(lazy deletion)를 조합해도 풀 수 있다. 다만 Java에서는 정렬된 key와 각 값의 개수를 함께 관리하는 TreeMap 하나가 더 단순하다.

필요한 것은 정렬된 다중 집합이다

문제의 연산은 세 가지다.

• I value: value 한 개 삽입
• D -1: 현재 최솟값 한 개 삭제
• D 1: 현재 최댓값 한 개 삭제

같은 값이 여러 번 들어올 수 있으므로 단순한 TreeSet은 맞지 않는다. TreeMap<Integer, Integer>에서 key를 값, value를 등장 횟수로 두면 중복을 잃지 않는다.

삽입        counts.merge(value, 1, Integer::sum)
최솟값      counts.firstKey()
최댓값      counts.lastKey()
한 개 삭제  count가 1이면 key 제거, 아니면 count 감소

각 연산은 서로 다른 key 수를 U라고 할 때 O(log U)다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        StringBuilder answer = new StringBuilder();

        for (int test = 0; test < testCount; test++) {
            int operationCount = Integer.parseInt(reader.readLine());
            TreeMap<Integer, Integer> counts = new TreeMap<>();

            for (int operation = 0; operation < operationCount; operation++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                char command = tokenizer.nextToken().charAt(0);
                int value = Integer.parseInt(tokenizer.nextToken());

                if (command == 'I') {
                    counts.merge(value, 1, Integer::sum);
                    continue;
                }

                if (counts.isEmpty()) {
                    continue;
                }

                int target = value == 1
                        ? counts.lastKey()
                        : counts.firstKey();
                removeOne(counts, target);
            }

            if (counts.isEmpty()) {
                answer.append("EMPTY\n");
            } else {
                answer.append(counts.lastKey())
                        .append(' ')
                        .append(counts.firstKey())
                        .append('\n');
            }
        }

        System.out.print(answer);
    }

    private static void removeOne(
            TreeMap<Integer, Integer> counts,
            int value
    ) {
        int count = counts.get(value);
        if (count == 1) {
            counts.remove(value);
        } else {
            counts.put(value, count - 1);
        }
    }
}

두 PriorityQueue를 쓴다면 무엇이 더 필요한가

최소 힙과 최대 힙에 같은 값을 넣어도 한쪽에서 삭제한 원소가 다른 쪽에는 남는다. 그래서 각 삽입에 고유 ID를 붙여 두 힙이 같은 항목을 가리키게 하거나, 값별 유효 개수를 두고 힙의 top에서 무효 항목을 계속 버리는 정리가 필요하다.

원문은 두 힙과 TreeMap을 동시에 사용했다. 동기화 문제를 알아낸 점은 맞지만, TreeMap이 이미 최솟값과 최댓값을 제공하므로 두 힙은 중복이었다. 문제 제목을 구현 지시로 읽지 말고, 필요한 추상 자료형이 무엇인지 먼저 적었으면 더 빨리 단순한 풀이에 도달할 수 있었다.

두 힙이 실제로 필요한 흐름은 백준 1655 가운데를 말해요, comparator가 핵심인 단일 힙 예시는 백준 11286 절댓값 힙에서 비교할 수 있다.

검증 범위

Java source를 수동 검토했다. 빈 자료구조 삭제, 중복값 연속 삽입·삭제, 음수와 32-bit 경계값을 포함한 무작위 연산을 정렬 배열 기반 기준 구현과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.