[백준] 이중 우선순위 큐 (TreeMap)
2022. 1. 17. 15:46ㆍ[ Basic ]/# 알고리즘
TreeMap
- Key-Value로 이루어진 entry를 Tree에 저장하는 자료구조
- Key를 기준으로 '정렬'한 형태의 Tree임 (~이진탐색트리)
- Tree중에서도 레드블랙트리를 기반으로 함(이진탐색트리에서 balanced tree)
- 즉, 모든 노드에서 왼쪽 서브트리의 값은 오른쪽 서브트리의 값보다 작음
- HashMap보다 성능이 떨어짐
- 하지만 정렬된 상태로 Map을 유지하거나 Key에 대해 범위 탐색을 할 경우 HashMap보다 유리함
cf. Heap과 구분해야 하는데, Heap은 루트 노드가 가장 우선순위를 큰 값을 갖는 형태지만 정렬되어 있지는 않음
- 최소 힙에서 최대값을 삭제하는 연산은 O(logN) 이라고 착각하기 쉬우나, O(N) 이 소요됨
- 이유는 힙은 정렬되어 있지 않기 때문에 모든 노드를 탐색해야 하기 때문
- 보통 레드블랙트리에서 첫 번째 요소는 그림에서 13이 아닌 1을 의미함 (레드블랙트리는 '정렬'되어 있기 때문)
- 따라서 TreeMap에서 firstEnrty() 메소드를 수행하면 트리에서 가장 왼쪽 노드의 값이 반환됨(lastEntry()는 반대)
백준 7662번 '이중 우선순위 큐'
코드
/******************************************************************************
문제출처 : https://www.acmicpc.net/problem/7662
풀이시간 : 20m
시간복잡도 : O(nlogn) (n: 입력 길이 <= 1,000,000)
공간복잡도 : O(n)
*******************************************************************************/
import java.io.*;
import java.util.*;
public class Main {
private static final String EMPTY = "EMPTY";
private static final String I = "I";
public static void main(String[] args) throws Exception {
var br = new BufferedReader(new InputStreamReader(System.in));
int tcNum = Integer.parseInt(br.readLine());
while (tcNum-- > 0) {
int commandNum = Integer.parseInt(br.readLine());
solve(br, commandNum);
}
}
private static void solve(BufferedReader br, int commandNum) throws Exception {
TreeMap<Integer, Integer> tm = new TreeMap<>(); // 기본적으로 오름차순 정렬
while (commandNum-- > 0) {
String[] commandToken = br.readLine().split(" ");
if (commandToken[0].equals(I)) {
int key = Integer.parseInt(commandToken[1]);
tm.put(key, tm.getOrDefault(key, 0) + 1);
continue;
}
Map.Entry<Integer, Integer> entry = commandToken[1].equals("-1") ? tm.firstEntry() : tm.lastEntry();
if (entry == null) continue;
if (entry.getValue() == 1) {
tm.remove(entry.getKey());
} else {
tm.replace(entry.getKey(), entry.getValue() - 1);
}
}
if (tm.isEmpty()) {
System.out.println(EMPTY);
return;
}
System.out.println(tm.lastKey() + " " + tm.firstKey());
}
}
Reference
- 백준 문제 링크 : https://www.acmicpc.net/problem/7662
'[ Basic ] > # 알고리즘' 카테고리의 다른 글
[백준] 2206 : DFS와 BFS차이 (0) | 2022.02.13 |
---|---|
크루스칼(MST) vs 다익스트라 비교 (0) | 2022.02.03 |
[DS] 레드블랙트리 (0) | 2022.01.11 |
[백준] 12919 시간복잡도 풀이 (0) | 2022.01.05 |
[BinarySearch] 백준 1920 (0) | 2021.08.04 |