[Baekjoon] 백준 7662: 이중 우선순위 큐 - Java

문제

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

 

풀이

TreeMap으로 정수와 정수의 개수를 저장한다.

TreeMap에는 firstKey와 lastKey라는 메소드가 존재해, 오름차순으로 정렬하는 TreeMap을 만들었을 경우, key 중에 제일 작은 값과 제일 큰 값은 가져올 수 있다.(firetKey(), lastKey())

삭제할 때, 기존의 개수가 1이었다면 제거하고 아니라면 기존 개수 - 1을 넣어준다. (덮어쓰기),

비어 있을 경우에는 무시하는 조건도 유의해야 한다.

 

시간복잡도는 T * log(1000000)이다.

 

소스코드

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

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

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

        StringBuilder sb = new StringBuilder();

        for (int test = 1; test <= t; test++) {
            int k = Integer.parseInt(br.readLine());

            TreeMap<Integer, Integer> map = new TreeMap<>();

            while (k > 0) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");

                String command = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                //입력
                if (command.equals("I")) {
                    map.put(n, map.getOrDefault(n, 0) + 1);
                }
                else {
                	//Q가 비어 있지 않을때 삭제되도록 함.
                    if (!map.keySet().isEmpty()) {
                        //최댓값
                        if (n == 1) {
                            int key = map.lastKey();

                            int value = map.get(key);

                            if (value == 1) {
                                map.remove(key);
                            }
                            else {
                                map.put(key, value - 1);
                            }
                        }
                        //최솟값
                        else {
                            int key = map.firstKey();

                            int value = map.get(key);

                            if (value == 1) {
                                map.remove(key);
                            }
                            else {
                                map.put(key, value - 1);
                            }
                        }
                    }
                }

                k -= 1;
            }

            if (map.keySet().isEmpty()) {
                sb.append("EMPTY");
            }
            //오름 차순 정렬했으므로, 최댓값 lastKey, 최솟값은 firstKey
            else {
                sb.append(map.lastKey()).append(" ").append(map.firstKey());
            }

            sb.append("\n");
        }

        System.out.print(sb);

        br.close();
    }
}