[BOJ_7662] 이중 우선순위 큐

설명

---

맞왜틀을 계속 시도했었던 문제 TestCase 새로 시작되면서 map을 당연히 초기화 해야하는데 그 생각을 못하고 계속 12%에서 틀렸었다.

 

어쨌든 Red Black Tree를 사용하는 TreeMap API를 활용하여서 OlogN으로 찾을 수 있었다. 또한, 최대 값과 최솟 값을 가져오기 정상적으로 가져오기 위해서 같은 수가 두 번 이상 들어올 때와 아예 사라질때 remove가 될때를 주의해서 구현하였다.

 

 

코드

---

package Data_Structure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class BOJ_7662 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int T = Integer.parseInt(tk.nextToken());
        TreeMap<Integer,Integer> map;
        while(T-- > 0){
            map = new TreeMap<>();
            tk = new StringTokenizer(in.readLine(), " ");
            int N = Integer.parseInt(tk.nextToken());
            while(N-- > 0){
                tk = new StringTokenizer(in.readLine(), " ");

                String str = tk.nextToken();

                int n = Integer.parseInt(tk.nextToken());

                if(str.equals("I")){
                    map.put(n, map.getOrDefault(n, 0) + 1);
                }else if (str.equals("D") && !map.isEmpty()){
                    if(n == -1) {
                    int minKey = map.firstKey();
                    if (map.get(minKey) == 1)
                    {
                        map.remove(minKey);
                    }else{
                        map.put(minKey,map.get(minKey)-1);
                    }
                    }else {
                        int maxKey = map.lastKey();
                        if (map.get(maxKey) == 1)
                        {
                            map.remove(maxKey);
                        }else{
                            map.put(maxKey,map.get(maxKey)-1);
                        }

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

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

7662번: 이중 우선순위 큐