이중 우선순위 큐

📍 문제 설명

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

7662번: 이중 우선순위 큐

 

💡 접근

문제 의도는 우선순위 큐 2개를 사용해서 풀라는 의도였지만 Treemap을 사용해서 더 편리하게 풀 수 있는 문제였다.

firstKey(), lastKey()를 처음 사용해보았다.

 

👩‍💻 코드

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

public class Main {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                char ch = st.nextToken().charAt(0);
                int n = Integer.parseInt(st.nextToken());

                if (ch == 'I') {
                    map.put(n, map.getOrDefault(n, 0) + 1);
                }
                else {
                    if(map.size() == 0) continue;
                    int key = (n == 1) ? map.lastKey() : map.firstKey();
                    if(map.get(key) == null) continue;
                    else if(map.get(key) == 1) map.remove(key);
                    else map.put(key, map.get(key)-1);
                }
            }
            if(map.size() == 0) System.out.println("EMPTY");
            else System.out.println(map.lastKey() + " " + map.firstKey());
        }
    }
}