[백준] 이중 우선순위 큐 (TreeMap)

TreeMap

- Key-Value로 이루어진 entry를 Tree에 저장하는 자료구조

- Key를 기준으로 '정렬'한 형태의 Tree임 (~이진탐색트리)

- Tree중에서도 레드블랙트리를 기반으로 함(이진탐색트리에서 balanced tree)

- 즉, 모든 노드에서 왼쪽 서브트리의 값은 오른쪽 서브트리의 값보다 작음

- HashMap보다 성능이 떨어짐

- 하지만 정렬된 상태로 Map을 유지하거나 Key에 대해 범위 탐색을 할 경우 HashMap보다 유리함

 

cf. Heap과 구분해야 하는데, Heap은 루트 노드가 가장 우선순위를 큰 값을 갖는 형태지만 정렬되어 있지는 않음

- 최소 힙에서 최대값을 삭제하는 연산은 O(logN) 이라고 착각하기 쉬우나, O(N) 이 소요됨

- 이유는 힙은 정렬되어 있지 않기 때문에 모든 노드를 탐색해야 하기 때문

 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

 

- 보통 레드블랙트리에서 첫 번째 요소는 그림에서 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