[Java] 백준 7662번 - TreeMap (시간복잡도 log n)

최근에 가장 고생한 문제였다.

원래 생각한 방법대로 우선순위 큐를 2개 사용하면 O(n)이라서 시간 초과되기 때문에

HashMap과 같으면서도 크기 순으로 정렬되어있는 TreeMap을 사용했다. (검색함...)

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

public class g1_7662 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            
            TreeMap<Integer, Integer> map = new TreeMap<>();
            // HashMap이 오름차순으로 정렬되어있다!!!
            for (int j = 0; j < N; j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                if (st.nextToken().equals("I")){
                    int temp = Integer.parseInt(st.nextToken());
                    if (!map.containsKey(temp)){
                        map.put(temp, 1);
                    }
                    else{
                        map.put(temp, map.get(temp) + 1);
                    }
                }
                else{
                    if (map.size() == 0) continue;
                    
                    int temp2;
                    if (st.nextToken().equals("1")){
                        temp2 = map.lastKey();
                        // lastKey : 마지막 key값 반환
                    }
                    else{
                        temp2 = map.firstKey();
                        // firstKey : 첫 key값 반환
                    }

                    if (map.get(temp2) == 1){
                        map.remove(temp2);
                    }
                    else{
                        map.put(temp2, map.get(temp2) - 1);
                    }
                }
            }

            if (map.size() == 0){
                bw.write("EMPTY");
            }
            else{
                bw.write(String.valueOf(map.lastKey()) + " " + String.valueOf(map.firstKey()));
            }
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }
}