[JAVA]백준_7662_이중 우선순위 큐

문제링크

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

 

 

package BOJ;

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

//7662 이중 우선순위 큐
public class Main_7662 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int t=0;t<T;t++) {
            TreeMap<Integer,Integer> treeMap = new TreeMap<>();
            int N = Integer.parseInt(br.readLine());

            for(int i=0;i<N;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                int number = Integer.parseInt(st.nextToken());
                
//                지정된 키의 값을 반환하며 찾지 못하면 기본값(defaultValue)로 지정된 객체를 반환한다
                if(str.equals("I")) treeMap.put(number,treeMap.getOrDefault(number,0)+1);
                else{
                    if(!treeMap.isEmpty()){
                        int num = (number == 1) ? treeMap.lastKey():treeMap.firstKey();
                        if(treeMap.put(num,treeMap.get(num)-1) ==1) treeMap.remove(num);
                    }
                }
            }
            System.out.println(treeMap.size() == 0 ?"EMPTY" : treeMap.lastKey()+" "+treeMap.firstKey());
        }

        }


}

 

제목이 이중우선순위 큐라서 PriorityQueue를 사용하여 해결하였었다.

내림차순으로 정렬하여 마지막 인덱스를 삭제할때는 reverseOrder라는 함수를 하나 만들어 큐에서 size>1이 될때까지 하나씩 빼면서 그 값을 새로운 큐에 넣어주는 방식을 사용했는데 그렇게 해결하니 시간초과가 발생했다!!

 

따라서 해결방법을 찾지못하고 인터넷에 검색해본 결과 TreeMap을 이용하는 방법이 있었다.

 

TreeMap은 일단 정렬된 상태로 입력이되며 firstKey,lastKey가 있어서 편하게 삭제를 할 수 있었다.