[JAVA] 백준 q7662 - 이중 우선순위 큐

7662번: 이중 우선순위 큐

---

> 의식의 흐름
시간 제한이 6초인 것을 보고 시간이 너무 널널한데? 생각했다가 T(테스트케이스의 수) 범위가 없는 것을 보고 PriorityQueue 2개를 쓰면 위험할 수도 있겠다는 생각을 했다. PriorityQueue 하나만 쓰는 방법을 생각하다가 TreeSet + PriorityQueue -> TreeMap 순으로 코드를 계속 수정했다,,

> 시간복잡도

# PriorityQueue
- 삽입, 삭제 : O(logN)

# Treemap
- 삽입, 삭제 : O(logN)
- containsKey() : O(logN)
- firstKey(), lastKey() : O(1)

참고 : https://zz132456zz.tistory.com/14

> 풀이 과정
1. 연산 유형이 'I'인 경우, TreeMap에 숫자 개수 갱신한다.
TreeMap<Integer, Integer> (key : 숫자, value : 숫자 개수)
2. 연산 유형이 'D'인 경우,
- TreeMap이 빈 상태라면, continue
- TreeMap에 값이 존재하는 상태라면, TreeMap에서 최대값/최소값 제거 후 개수 갱신한다.
-> TreeMap에 1개만 존재하는 값이라면, TreeMap에서 제거한다.
-> TreeMap에 2개 이상 존재하는 값이라면, '기존 개수 - 1'로 갱신한다.
3. k(연산 개수)만큼 1~2번 과정 반복한다.
4. TreeMap이 빈 상태인 경우, "EMPTY" 출력한다.
5. TreeMap에 값이 존재하는 경우, "최댓값 최솟값" 출력한다.
6. T(테스트케이스 수)만큼 1~5번 과정 반복한다.

 

> 코드

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

public class Main {
    public static int T; // 테스트케이스의 수

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        while(T-->0){
            int k = Integer.parseInt(br.readLine()); // 연산 개수
            TreeMap<Integer,Integer> nums = new TreeMap<>();

            // Q에 대한 연산 수행
            while(k-->0) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                char type = st.nextToken().charAt(0); // 연산 유형
                int num = Integer.parseInt(st.nextToken()); // 유형 이후 숫자

                if (type == 'I') { // 삽입인 경우
                    if (nums.containsKey(num)) {
                        nums.put(num, nums.get(num) + 1);
                    } else {
                        nums.put(num, 1);
                    }
                }
                else if (type == 'D') { // 삭제인 경우
                    if(nums.keySet().isEmpty()){
                        continue;
                    }

                    int removedNum = 0;
                    if (num == 1) { // 최댓값 삭제
                        removedNum = nums.lastKey();
                    }
                    else { // 최솟값 삭제
                        removedNum = nums.firstKey();
                    }

                    int numCnt = nums.get(removedNum); // 제거한 값의 기존 개수
                    if (numCnt == 1) { // 1개인 경우
                        nums.keySet().remove(removedNum); // TreeMap에서 제거
                    }
                    else { // 2개 이상인 경우
                        nums.put(removedNum, numCnt - 1); // TreeMap에서 개수 줄이기
                    }
                }
            }

            if(nums.keySet().isEmpty()) { // 빈 경우
                bw.write("EMPTY\n");
            }
            else {
                bw.write(Integer.toString(nums.lastKey())+" "+Integer.toString(nums.firstKey())+"\n");
            }
        }
        bw.flush();

        br.close();
        bw.close();
    }
}