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

[문제]

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

7662번: 이중 우선순위 큐

 

[풀이]

이전 프로그래머스 풀이대로 minHeap과  maxHeap 두개를 이용해 구현하면 시간초과가 발생한다. 

시간초과가 발생하는 이유는 다른 우선순위큐의 원소를 제거하기 위해 remove()를 사용할 경우 O(N)이 소요되기 때문이다. 따라서 우선순위큐가 아닌 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());
            }
        }
    }
}