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

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

7662번: 이중 우선순위 큐

 

중복되는 값들을 카운트할 HashMap과 오름차순 우선순위 큐, 내림차순 우선순위 큐를 만들어

입력 값이 I 일때

중복되는 값이 HashMap에 없으면 양쪽 큐에 다 넣고

중복되는 값이 HashMap에 있으면 value를 1 증가한다

입력 값이 D 일때

HashMap에 peek 값이 있고 value가 1보다 크면 value를 1 빼고

value가 1이면 HashMap에서 제거하고, 큐에서도 poll한다

 

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            sb.append(dualQueue()).append("\n");
        }
        System.out.println(sb);
    }

    static String dualQueue() throws IOException {
        String result = "EMPTY";
        int Q = Integer.parseInt(br.readLine());
        Queue<Integer> maxQueue = new PriorityQueue<>(((o1, o2) -> o2 > o1 ? 1 : -1));
        Queue<Integer> minQueue = new PriorityQueue<>();
        Map<Integer, Integer> count = new HashMap<>();
        for (int q = 0; q < Q; q++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int k = Integer.parseInt(st.nextToken());
            if (str.equals("I")) {
                if (count.containsKey(k)) count.replace(k, count.get(k) + 1);
                else {
                    count.put(k, 1);
                    minQueue.add(k);
                    maxQueue.add(k);
                }
            } else {
                if (k == 1) {
                    while (!count.isEmpty() && count.getOrDefault(maxQueue.peek(), 0) == 0) maxQueue.poll();
                    if (!count.isEmpty()) {
                        int peek = maxQueue.peek();
                        if (count.get(peek) == 1) {
                            maxQueue.poll();
                            count.remove(peek);
                        }
                        else count.replace(peek, count.get(peek) - 1);
                    }
                } else {
                    while (!count.isEmpty() && count.getOrDefault(minQueue.peek(), 0) == 0) minQueue.poll();
                    if (!count.isEmpty()) {
                        int peek = minQueue.peek();
                        if (count.get(peek) == 1) {
                            minQueue.poll();
                            count.remove(peek);
                        }
                        else count.replace(peek, count.get(peek) - 1);
                    }
                }
            }
        }
        while (!count.isEmpty() && count.getOrDefault(maxQueue.peek(), 0) == 0) maxQueue.poll();
        while (!count.isEmpty() && count.getOrDefault(minQueue.peek(), 0) == 0) minQueue.poll();
        return count.isEmpty() ? result : String.format("%d %d", maxQueue.peek(), minQueue.peek());
    }
}

 

maxQueue의 정렬방식에 평소에는 o2 - o1을 사용하다가 이번엔 o2 > o1 ? 1 : -1로 하였는데

int의 최대값과 최소값인 −2,147,483,648와 2,147,483,647을 넣었을 때

maxQueue의 peek값이 −2,147,483,648이 나왔다 (2,147,483,647이 나와야함)

o2 - o1을 하면서 int의 범위를 벗어나 원하는 값이 안나온 것 같다

 

 

이중 우선순위 큐가 문제 이름이라서 우선순위 큐를 2개 만들어서 사용했는데

시간도 오래걸리고, 공간도 많이 잡아먹는다

다른 사람 풀이를 보니 TreeMap을 사용하여 우선순위 큐를 만들지 않고 TreeMap의 양 끝 값을 사용했다