(boj) 백준골드4 7662 이중 우선순위 큐(Java) – TreeMap

(문제)

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

(설명)

이전 프로그래머의 솔루션에서와 같이 두 개의 minHeap 및 maxHeap을 사용한 구현이 시간 초과되었습니다.

다른 우선 순위 대기열에서 항목을 제거하기 위해 remove()를 사용할 때 O(N)이 필요하기 때문에 시간 초과가 발생합니다. 따라서 Priority Queue 대신 TreeMap을 사용하면 원하는 항목을 바로 찾아서 제거할 수 있다.

(암호)

package heap_stack_dequeue;

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

public class boj_7662_java{
    static int t;
    public static void main(String() args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        while(t-->0){
            int n = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> tm = new TreeMap<>();
            for(int i=0; i<n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                char order = st.nextToken().charAt(0);
                if(order=='I'){
                    int num = Integer.parseInt(st.nextToken());
                    tm.put(num, tm.getOrDefault(num, 0)+1);
                }
                else if(!tm.isEmpty()){
                    int option = Integer.parseInt(st.nextToken());
                    if(option==1){
                        //최댓값 삭제
                        int num = tm.lastKey();
                        if(tm.get(num)==1){
                            tm.remove(num);
                        }
                        else{
                            tm.put(num, tm.get(num)-1);
                        }
                    }
                    else{
                        //최솟값 삭제
                        int num = tm.firstKey();
                        if(tm.get(num)==1){
                            tm.remove(num);
                        }
                        else{
                            tm.put(num, tm.get(num)-1);
                        }
                    }
                }
            }

            if(tm.isEmpty()){
                System.out.println("EMPTY");
            }
            else{
                System.out.println(tm.lastKey() + " " + tm.firstKey());
            }
        }
    }
}