[Algorithm/Java] 백준 7662번 - 이중 우선순위 큐
https://www.acmicpc.net/problem/7662
📌 문제
문제 유형
- 자료 구조
문제 설명
입력
2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333
출력
EMPTY
333 -45
🔍 문제 풀이
자바의 PriorityQueue는 최소 힙만 지원하기 때문에, 최대값을 함께 관리하려면 굉장히 복잡하다.
TreeMap<Integer, Integer>
를 사용하면 자동 정렬 기능과 함께 중복 값도 개수로 관리할 수 있어,
이중 우선순위 큐를 훨씬 쉽고 간단하게 구현할 수 있다.
🌳 TreeMap이란?
TreeMap
은 key를 자동 정렬해주는 Map 자료구조이다.- 내부적으로 Red-Black Tree(이진 탐색 트리) 기반으로 구현되어 있다.
- key 중복은 허용되지 않으므로, value에 개수를 저장해 중복을 관리한다.
firstKey()
와lastKey()
를 통해 최솟값과 최댓값을 O(log N)에 가져올 수 있다.
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(5, 1);
map.put(2, 1);
map.put(7, 1);
System.out.println(map.firstKey()); // 2 (최솟값)
System.out.println(map.lastKey()); // 7 (최댓값)
key 중복은 허용하지 않으므로, 중복값은 다음처럼 value로 개수를 관리한다.
map.put(5, map.getOrDefault(5, 0) + 1); // 5가 없으면 0, 있으면 기존 개수 +1
삭제 처리도 value로 개수를 관리한다.
int count = map.get(5);
if (count == 1) map.remove(5);
else map.put(5, count - 1);
📌 놓친 점
처음에는 TreeMap이 있는줄 모르고 PriorityQueue로 풀려고 했다가, 도저히 풀리지가 않았다.
그러다가 검색을 통해 정렬과 중복 카운팅을 동시에 처리할 수 있다는 TreeMap
이라는 자료 구조를 알게 되었다.
💻 전체 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t --> 0){
TreeMap<Integer, Integer> map = new TreeMap<>();
int k = Integer.parseInt(br.readLine());
while (k-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
String command = st.nextToken();
int n = Integer.parseInt(st.nextToken());
if(command.equals("I")){
map.put(n, map.getOrDefault(n, 0) + 1);
} else if(command.equals("D")) {
if(map.isEmpty()) continue;
// 삭제할 대상 key 선택 (삭제는 아직 하지 않음)
int key=0;
if (n == 1) {
key = map.lastKey(); // 최댓값 key 가져오기
} else {
key = map.firstKey(); // 최솟값 key 가져오기
}
// 삭제
int count = map.get(key);
if (count == 1) {
map.remove(key); // 개수가 1개 -> key 자체 삭제
} else {
map.put(key, count - 1); // 개수가 여러 개 -> value만 1 감소
}
}
}
if (map.isEmpty()) {
System.out.println("EMPTY");
} else {
System.out.println(map.lastKey() + " " + map.firstKey());
}
}
}
}
댓글남기기