[Algorithm] 백준_이중 우선순위 큐_7662번 (JAVA) TreeMap

📝문제

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

이중 우선순위 큐 7662번

티어: 골드 4

💡풀이

문제 유형

자료 구조
트리를 사용한 집합과 맵
우선순위 큐

 

걸린 시간

60분

 

시간 복잡도

O(T×klogk)

 

풀이 방법 도출

1. deque를 이용해서 시도했다가 시간초과 에러가 났고 우선순위 큐를 이용하려다 실패하고 결국 TreeMap이라는 자료구조를 사용하게 되었다.
2. TreeMap이란 정렬된 맵으로 항상 키가 정렬된 상태로 유지되며, O(log N)의 시간 복잡도로 데이터를 삽입, 삭제, 조회할 수 있다. HashMap의 정렬된 버전이라고 생각하면 쉽다. (HashMap보다 삽입/삭제는 느리지만 정렬된 데이터를 다룰 때 훨씬 효율적이다.)
   1. firstKey(): 최솟값 찾기
   2. lastKey(): 최댓값 찾기
   3. pollFirstEntry(): 최솟값 삭제
   4. pollLastEntry(): 최댓값 삭제
3.  treeMap을 선언 후 key에는 n을, value에는 n의 개수를 넣어준다.
4. D가 입력되면 -1일떄는 firstKey()를, 1일 때는 lastKey()를 사용해 key를 찾고 
5. 해당 key의 value값이 1이면 삭제해주고, 1이 아니라면 기존 value값에 -1을 해주고, 이를 반복한다.
6. 이후 treeMap에 남은 key들 중 fistKey()와 lastKey()를 찾아주면 된다.

import java.util.*;
import java.io.*;
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 i = 0; i < T; i++){
            TreeMap<Integer, Integer> treeMap = 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 n = Integer.parseInt(st.nextToken());
                if("I".equals(command)){
                    treeMap.put(n, treeMap.getOrDefault(n,0)+1);
                }
                if("D".equals(command)){
                    if(treeMap.isEmpty()) continue;
                    int key = 0;
                    if(n == 1){//최대값
                        key = treeMap.lastKey();
                    }
                    if(n == -1){//최솟값
                        key = treeMap.firstKey();
                    }
                    if(treeMap.get(key) == 1){
                        treeMap.remove(key);
                    }else{
                        treeMap.put(key, treeMap.get(key)-1);
                    }
                }
            }
            if(treeMap.isEmpty()){
                sb.append("EMPTY");
            }else{
                sb.append(treeMap.lastKey()).append(" ").append(treeMap.firstKey());
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

🤔Review

TreeMap의 개념을 잘 몰랐는데 이 문제를 통해서 개념을 짚고 넘어간다. 🌳