[백준/JAVA] 7662번: 이중 우선순위 큐

🔺 문제

7662번: 이중 우선순위 큐

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
        while(T -- > 0) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> tree = new TreeMap<>();
            
            while(k --> 0) {
                st = new StringTokenizer(br.readLine(), " ");
                
                String cmd = st.nextToken();
                int n = Integer.parseInt(st.nextToken());
                
                // 삽입
                if(cmd.equals("I")) {
                    tree.put(n, tree.getOrDefault(n, 0) + 1);
                }
                // 삭제
                else {
                    if(tree.size() == 0) continue;
 
                    int num = (n == 1) ? tree.lastKey() : tree.firstKey();                    
                    if(tree.put(num, tree.get(num) - 1) == 1)    // 해당 정수의 갯수를 -1하면서 만약 0이 된다면 삭제
                        tree.remove(num);
                }
            }
            
            sb.append(tree.size() == 0 ? "EMPTY" : tree.lastKey() + " " + tree.firstKey()).append("\n");
        }
        
        System.out.println(sb);
    }
}
 

✅ 해결 아이디어
✔ TreeMap

 

< TreeMap 특징 > 

- Red-Black Tree로 구성되어 있음 (이진 트리의 일종)
- Key 값 기준으로 정렬된 상태 유지 (default : 오름차순 !) → firstKey(), lastKey() 로 양 끝 값에 편리하게 접근 가능

- 시간 복잡도 : O(log N)

 

🚩 put() :  이전에 저장 되어있던 해당 키값과 같은 키를 저장하면, 저장되어있던 key의 value 값 반환.

                              (이전 값이 존재하지 않으면, null 반환) 

 

---

🔺 다른 풀이들

- 약간 풀어놓은 설명 굿...

[백준 7662번] 이중 우선순위 큐 - java

 

---

💬 느낀 점

처음에 Deque 사용하려다 시간 초과 떠서 틀리구

풀이를 찾아봤더니

TreeMap을 써야한다고...

 

이렇게 하나 또 배우고 갑니다... (꾸벅)

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이

[BOJ] 7662 - 이중 우선순위 큐 JAVA

[JAVA / 자바] 백준 7662번 - 이중 우선순위 큐 (골드 5)

 

 

✔ TreeMap 사용법

[Java] 자바 TreeMap 사용법 & 예제 총정리