BOJ에서 이중 우선순위큐라는 최대힙과 최소힙 을 사용하여 최댓값과 최소값을 출력하는 알고리즘 문제를 풀면서 시간초과로 인하여 '6초라는 시간이 있는데 시간초과가 나오네?' 라는 의문점과 함께 구글링을 하던 중 TreeMap이라는 구조가 있다는 것을 알게 되었고, TreeSet과 TreeMap 중 중복된 값을 '허용' 한다는 조건이 있어 TreeSet이 아닌 TreeMap을 사용하여 TreeMap에 대해서 포스팅 하였습니다.
일단❗Tree란?
맨 위의 시작 노드를 보통 루트(root)라고 불리며, 나머지는 n개의 자식 노드들로 구성되어 있다. (하위 노드 위에 루트 노드를 제외한 인접한 상위 노드가 있다면 그 상위 노드를 부모 노드라고 부르기도 한다.) 해당 구조를 자세히 보면 같은 자식이라도 왼쪽은 작은 자식 오른쪽은 큰 자식이라고 된 것을 볼 수 있는데, 부모(상위) 노드를 기준으로 큰 값은 우측 작은 값은 좌측에 저장됩니다.
🎯TreeMap이란?
TreeMap은 이진트리를 기반으로 한 Map 컬렉션입니다. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Entry를 저장한다는 점입니다. TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장합니다. TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다. TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸립니다. 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋습니다.
TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있습니다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요합니다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 냅니다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였습니다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다.
이러한 특성 때문에 삽입, 삭제가 빈번하게 일어나는 이번 문제에서 적합하다고 판단하였습니다.
또한 TreeMap 은 firstKey값(최소값), lastKey값(최대값) 메소드로 인하여 tree의 최소값과 최대값을 가져오는데 효과적이었습니다.
- BOJ - 7662 이중 우선순위 큐
https://www.acmicpc.net/problem/7662
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
-------------------------------------------------------------------------------
// 시간초과
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringBuilder sb = new StringBuilder();
// Deque<Integer> deque;
// PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
//
//
// int n = Integer.parseInt(br.readLine());
//
// for(int i=0;i<n;i++){
// int m = Integer.parseInt(br.readLine());
// deque = new ArrayDeque<>();
// for(int j=0;j<m;j++){
// String[] str = br.readLine().split(" ");
//
// if(str[0].equals("I")){
// if(deque.isEmpty()){
// deque.add(Integer.parseInt(str[1]));
// }
// else if(deque.peekFirst() >= Integer.parseInt(str[1]))
// deque.addFirst(Integer.parseInt(str[1]));
// else if(deque.peekLast() <= Integer.parseInt(str[1]))
// deque.addLast(Integer.parseInt(str[1]));
// else {
//// ArrayList<Integer> arr = new ArrayList<>();
// while (true) {
// pq.add(deque.pollLast());
// if(deque.peekLast() <= Integer.parseInt(str[1])) {
// deque.addLast(Integer.parseInt(str[1]));
// break;
// }
// }
// }
// }
// else if(str[0].equals("D")){
// if(Integer.parseInt(str[1]) == -1) {
// if (!deque.isEmpty())
// deque.pollFirst();
// else {
// for(int k = 0 ; k<pq.size()-2;k++)
// pq.add(pq.poll());
// pq.poll();
// }
// }
// else
// if(pq.isEmpty())
// deque.pollLast();
// else
// pq.poll();
// }
// }
// if(deque.isEmpty() && pq.isEmpty())
// sb.append("EMPTY\n");
// else if(deque.size() >= 1 && pq.size() >= 1)
// sb.append(pq.poll() + " " + deque.pollFirst());
// else if(pq.size() == 0 && deque.size() > 1)
// sb.append(deque.pollLast() + " " + deque.pollFirst());
// else {
// int equal;
// if(deque.isEmpty() && !pq.isEmpty())
// equal = pq.poll();
// else
// equal = deque.poll();
// sb.append(equal + " " + equal);
// }
//
// }
// System.out.println(sb);
-------------------------------------------------------------------------------
// remove(Object o)로 인하여 O(N)이 되어 시간초과
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// StringBuilder sb = new StringBuilder();
// PriorityQueue<Integer> minQueue;
// PriorityQueue<Integer> maxQueue;
//
//
// int n = Integer.parseInt(br.readLine());
//
// for(int i=0;i<n;i++) {
// minQueue = new PriorityQueue<>();
// maxQueue = new PriorityQueue<>(Collections.reverseOrder());
// int m = Integer.parseInt(br.readLine());
// for (int j = 0; j < m; j++) {
// String[] str = br.readLine().split(" ");
//
// if(str[0].equals("I")){
// minQueue.add(Integer.parseInt(str[1]));
// maxQueue.add(Integer.parseInt(str[1]));
// }
// else{
// if(Integer.parseInt(str[1]) == -1){
// if(!minQueue.isEmpty()) {
// int min = minQueue.poll();
// maxQueue.remove(min);
// }
// }
// else {
// if(!maxQueue.isEmpty()) {
// int max = maxQueue.poll();
// minQueue.remove(max);
// }
// }
// }
// }
//
// if(minQueue.isEmpty() && maxQueue.isEmpty())
// sb.append("EMPTY\n");
// else
// sb.append(maxQueue.poll() + " " + minQueue.poll());
// }
// System.out.println(sb);
-------------------------------------------------------------------------------
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
TreeMap<Integer, Integer> map = new TreeMap<>();
int m = Integer.parseInt(br.readLine());
for (int j = 0; j < m; j++) {
String[] str = br.readLine().split(" ");
if(str[0].equals("I")){
map.put(Integer.parseInt(str[1]),map.getOrDefault(Integer.parseInt(str[1]),0)+1); // 현재 수가 없으면 생성, 있으면 카운트 증가
}
else {
if(map.isEmpty()) continue;
int num;
if(Integer.parseInt(str[1]) == 1)
num = map.lastKey();
else num = map.firstKey();
if(map.put(num,map.get(num)-1) == 1)
map.remove(num);
}
}
if(map.isEmpty()) sb.append("EMPTY\n");
else sb.append(map.lastKey() + " " + map.firstKey() + "\n");
}
System.out.println(sb);
}
}