[백준] 7662 이중 우선순위 큐 자바(Java)

7662번: 이중 우선순위 큐

 

풀이

• TreeMap 자료 구조를 사용한다.
  • TreeMap은 키값을 기준으로 즉시 정렬되는 자료 구조입니다.
• key = 정수, value = 입력된 횟수
• 최댓값(최솟값)의 입력 횟수가 2번 이상일 때는 입력 횟수 -1, 입력된 횟수가 1번이면 삭제한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringBuffer sb = new StringBuffer();

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

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            TreeMap<Integer, Integer> map = new TreeMap<>();
            while (n-- > 0) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");

                String in = st.nextToken();
                int val = Integer.parseInt(st.nextToken());

                if (in.equals("I")) {
                    map.put(val, map.getOrDefault(val, 0) + 1);
                } else {
                    if (map.isEmpty()) {
                        continue;
                    }
                    int key = -1;
                    if (val == 1) {
                        key = map.lastKey();
                    } else {
                        key = map.firstKey();
                    }
                    // 여기서 map.put(key, value ) == 1 은 map.get(key)와 같은 결과입니다.
                    // 기존에 key가 가지고 있는 값을 반환해줍니다.
                    // 즉, 입력된 횟수가 1회이면 지우고 그 외의 값은 value(입력 횟수)만 -1 합니다.
                    if (map.put(key, map.get(key) - 1) == 1) {
                        map.remove(key);
                    }
                }
            }
            if (map.isEmpty()) {
                sb.append("EMPTY").append("\n");
            } else {
                sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
            }
        }

        System.out.println(sb);
    }
}