문제
정수를 삽입하고 최댓값 또는 최솟값을 삭제하는 연산을 지원하는 이중 우선순위 큐를 구현하라.
입력
첫째 줄에 테스트 케이스 수 T. 각 테스트 케이스의 첫째 줄에 연산 수 K, 이후 K줄에 "I n" (삽입) 또는 "D 1" (최대 삭제) / "D -1" (최소 삭제) 연산이 주어진다.
출력
각 테스트 케이스마다 큐가 비어있으면 "EMPTY", 아니면 최댓값과 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 7 I 16 I 123 D 1 D 1 D -1 I 5 I 7 2 I -45 I 653 | 7 5 EMPTY |
풀이
TreeMap을 사용하여 정렬된 상태를 유지하며 최대/최소 삭제를 O(log N)에 수행한다.
TreeMap에 값과 개수를 저장한다 (중복값 처리)- 삽입 시 해당 값의 개수를 1 증가시킨다
- 최대 삭제 시
lastKey(), 최소 삭제 시firstKey()로 접근한다 - 개수가 0이 되면 키를 제거한다
핵심 아이디어: TreeMap은 레드-블랙 트리 기반으로 최대/최소를 O(log N)에 접근할 수 있어 이중 우선순위 큐에 적합하다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day584BOJ7662이중우선순위큐 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int test = 0; test < t; test++) {
int input = Integer.parseInt(br.readLine());
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < input; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String op = st.nextToken();
if (op.equals("I")) {
int num = Integer.parseInt(st.nextToken());
map.put(num, map.getOrDefault(num, 0) + 1);
} else {
if (map.size() == 0)
continue;
int type = Integer.parseInt(st.nextToken());
int num;
if (type == 1) { // 최댓값 삭제
num = map.lastKey();
} else { // 최솟값 삭제
num = map.firstKey();
}
if (map.put(num, map.get(num) - 1) == 1) {
map.remove(num);
}
}
}
if (map.size() == 0) {
sb.append("EMPTY\n");
} else {
sb.append(map.lastKey() + " " + map.firstKey() + "\n");
}
}
System.out.println(sb.toString());
}
}복잡도
- 시간: O(K log K) - K는 연산 수
- 공간: O(K)