[Baekjoon] 7662: 이중 우선순위 큐

문제

삽입 연산과 삽입된 값들 중에 최대값과 최소값 삭제 연산을 통해 최종적으로 남아있는 최대값과 최소값을 출력하는 문제이다.

문제 제목 자체가 이중 우선순위 큐로 힌트를 주기 때문에, 좀 더 풀이가 쉽지 않았나 생각한다.

 

풀이

내 풀이

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

public class Q7662 {
    private static BufferedReader br;
    private static StringBuilder sb;

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

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            testCase();
        }

        System.out.print(sb);
    }

    public static void testCase() throws IOException {
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> minpq = new PriorityQueue<>(Comparator.comparingInt(v -> v));
        Queue<Integer> maxpq = new PriorityQueue<>((v1, v2) -> -(v1.compareTo(v2)));
        Map<Integer, Integer> counts = new HashMap<>();

        int count = 0;
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            String command = input[0];
            int x = Integer.parseInt(input[1]);

            if (command.equals("I")) {
                minpq.offer(x);
                maxpq.offer(x);
                counts.put(x, counts.getOrDefault(x, 0) + 1);
                count++;
                continue;
            }

            if (count == 0) {
                maxpq.clear();
                minpq.clear();
                counts.clear();
                continue;
            }

            if (x == 1) {
                while (!maxpq.isEmpty()) {
                    int maxValue = maxpq.poll();
                    if (counts.getOrDefault(maxValue, 0) > 0) {
                        counts.put(maxValue, counts.get(maxValue) - 1);
                        count--;
                        if (count == 0) {
                            maxpq.clear();
                            minpq.clear();
                            counts.clear();
                        }
                        break;
                    }
                }
                continue;
            }

            while (!minpq.isEmpty()) {
                int minValue = minpq.poll();
                if (counts.getOrDefault(minValue, 0) > 0) {
                    counts.put(minValue, counts.get(minValue) - 1);
                    count--;
                    if (count == 0) {
                        maxpq.clear();
                        minpq.clear();
                        counts.clear();
                    }
                    break;
                }
            }
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > 0) {
                int key = entry.getKey();
                max = Math.max(max, key);
                min = Math.min(min, key);
            }
        }

        if (count == 0) {
            sb.append("EMPTY").append("\n");
            return;
        }

        sb.append(max).append(" ").append(min).append("\n");
    }
}

풀이는 기본적으로 널리 알려진 풀이지만, PriorityQueue 비교 연산에서 한참 헤멘 것 같다.

 

습관적으로 최대, 최소 우선순위 큐를 만들 때 다음과 같이 만든다.

Queue<Integer> minpq = new PriorityQueue<>(Comparator.comparingInt(v -> v));
Queue<Integer> maxpq = new PriorityQueue<>(Comparator.comparingInt(v -> -v));

그런데 하나 간과한 것이 있었다.

Integer의 양 끝 값인 -2147483648와 2147483647이 들어갈 때 문제가 생겼다.

내림차순으로 정렬하기 위해 -v로 비교하면 -2147483647과 2147483648이 비교가 되는데, 여기서 2147483648은 Integer의 최대 범위를 넘어 다시 -값이 되어 버린다.

 

때문에 다음과 같이 수정해서 작성했다.

Queue<Integer> minpq = new PriorityQueue<>(Comparator.comparingInt(v -> v));
Queue<Integer> maxpq = new PriorityQueue<>((v1, v2) -> -(v1.compareTo(v2)));

 

회고

위에서 말했던 대로 미처 체크하지 못한 overflow로 인해 고생 좀 한 것 같다. 앞으로 비교 연산 시에 integer 경계값을 잘 고려해야겠다.