자바 - 백준 7662 / 이중 우선순위 큐

자바 - 백준 7662 / 이중 우선순위 큐
골드4

구현 방법

연산의 범위가 최대 1,000,000이내 이고, 이런 테스트 케이스가 여러개 나옵니다.
따라서 최댓값과 최솟값을 항상 관리하면서 연산을 수행하는 것이 좋다고 판단했습니다.
방법은 첫번째로 우선순위 큐 두개를 이용하여 최댓값 최소값을 값을 삽입할 때마다 최신 상태로 유지하는것 입니다. 이러면 삽입 때마다 O(log n)의 시간복잡도가 걸립니다.


두번째로 두 우선순위큐를 동기화 시키며 일관성을 유지해야 합니다. 여기서 처음에 잘못 생각했습니다.


잘못된 방법
최댓값, 최솟값을 삭제할 때마다 min, max에 가장 최근에 삭제한 값을 저장해 놓았습니다.
이렇게 한 뒤 최댓값이나 최솟값을 삭제할 때마다 min, max와 비교하여 값이 같거나 큰 경우 삭제를 못하도록 했습니다. 이렇게 구현 할 경우 같은 값이 여러개가 있는 경우에 대한 처리를 할 수가 없었습니다.


올바른 방법
데이터 삽입시 두 우선순위큐에 넣을 뿐 아니라 map<삽입 데이터, 갯수>를 함께 저장합니다. 그 후 삭제 연산에 map 데이터의 갯수와 함께 비교하여 연산을 수행합니다. 이렇게 두 우선순위 큐의 데이터를 동기화 했습니다.

코드

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

/**
 * 백준 7662
 * 이중 우선순위 큐
 * 골드4
 * https://www.acmicpc.net/problem/7662
 */
public class Boj7662 {

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

        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t < T; t++) {
            int k = Integer.parseInt(br.readLine());

            PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> minPQ= new PriorityQueue<>();
            Map<Integer, Integer> cnt = new HashMap<>();

            while(k --> 0) {
                st = new StringTokenizer(br.readLine());

                String s = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if(s.equals("I")) {

                    maxPQ.add(n);
                    minPQ.add(n);
                    cnt.put(n, cnt.getOrDefault(n, 0) + 1);
                } else {
                    if(cnt.isEmpty())
                        continue;

                    if(n == 1) {
                        remove(maxPQ, cnt);
                    } else {
                        remove(minPQ, cnt);
                    }
                }
            }

            if(cnt.isEmpty()) {
                sb.append("EMPTY").append("\n");
            } else {
                int answer = remove(maxPQ, cnt);
                sb.append(answer).append(" ");

                if(!cnt.isEmpty())
                    answer = remove(minPQ, cnt);
                sb.append(answer).append("\n");
            }
        }
        System.out.print(sb);
    }

    private static int remove(PriorityQueue<Integer> pq, Map<Integer, Integer> map) {
        int cur;
        while(true) {
            cur = pq.poll();
            int count = map.getOrDefault(cur, 0);
            if(count == 0) continue;
            if(count == 1) map.remove(cur);
            else map.put(cur, count - 1);
            break;
        }
        return cur;
    }
}