백준 7662 자바 - 이중 우선순위 큐

// 이중 우선순위 큐
package Gold_IV_4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Ex7662 {
    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 i = 0; i < t; i++) {
            TreeMap<Integer, Integer> map = new TreeMap<>();

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

            for (int j = 0; j < k; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());

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

                if (command.equals("I")) {
                    map.put(num, map.getOrDefault(num, 0)+1);
                } else if (command.equals("D")) {
                    if (!map.isEmpty()) {
                        int count = 0;
                        if (num == 1) {
                            count = map.lastKey();
                        } else if (num == -1) {
                            count = map.firstKey();
                        }
                        map.put(count, map.get(count) - 1);
                        if (map.get(count) == 0) {
                            map.remove(count);
                        }
                    }
                }
            }

            if (map.isEmpty()) {
                sb.append("EMPTY").append("\n");
            } else {
                sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
            }
        }
        System.out.print(sb);
    }
}

이번 문제는 아래 블로그를 참고했다.

[BOJ] 백준 7662번 이중 우선순위 큐 (Java) (tistory.com)

[BOJ] 백준 7662번 이중 우선순위 큐 (Java)

 

여러 방법을 시도하면서 나도 우선순위 큐 두개와 map을 사용하는 방법을 생각해 봤지만, 구현방식이 안 떠올랐다. treeMap을 사용하는 것도 생각해 봤지만, 최소 키와 최대 키만 찾는걸 보고 안 된다고 생각했다.

 

코드 설명

map.put(num, map.getOrDefault(num, 0)+1);

map의 key 값이 value라고 생각하면 편하다. 즉, map.put(value, 개수) 이런 것이다. num이 처음 들어오는 수면 1을 put하고, 원래 있던 수면 기존 개수에 +1을 해서 put한다.

 

// 내 코드
map.put(count, map.get(count) - 1);
if (map.get(count) == 0) {
	map.remove(count);
}

// 블로그 코드
if(map.put(count, map.get(count)-1)==1) {
	map.remove(count);
}

내가 참고한 블로그에서는 원래 저렇게 돼 있었는데, 난 map.put에 put 이전 값을 return 한다는 점이 생소해서 위처럼 풀었다.