[JAVA/알고리즘] TreeMap 트리 맵 (백준 7662)

1) TreeMap 이란

TreeMap이란 이진트리를 기반으로 한 Map 컬렉션이다. 

 

 

위 사진처럼 레드-블랙 트리로 구현되어 있어

기본적으로 TreeMap에 객체를 삽입하면, key값을 기준으로 오름차순 정렬되어 저장된다.

 

 

TreeMap은 HashMap보다 추가, 삭제 시간이 오래 걸린다. 

	HashMap	TreeMap
조회	평균 :  O(1) / 최악 : O(n)	O(log n)
추가	평균 :  O(1) / 최악 : O(n)	O(log n)
삭제	평균 :  O(1) / 최악 : O(n)	O(log n)

 

 

2) TreeMap의 Method

import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        // 값 삽입
        map.put(1, 1);
        map.put(2, -1);
        map.put(-44, 5);

        // 첫번쨰 키 값 조회 (가장 작은 수)
        int minKey = map.firstKey();
        System.out.println("minKey: " + minKey);

        // 마지막 키 값 조회 (가장 큰 수)
        int maxKey = map.lastKey();
        System.out.println("maxKey: " + maxKey);

        // 최소 키 값을 가진 key-value 쌍 삭제
        map.pollFirstEntry();
        System.out.println("size: " + map.size());

        // 최소 키 값을 가진 key-value 쌍 삭제
        map.pollLastEntry();
        System.out.println("size: " + map.size());
    }
}

 

 

삽입, 조회 등의 기본 메서드들은 HashMap의 메서드와 같다. 

 

정렬되어 있는 수 중 최솟값, 최댓값의 수를 조회하고 삭제 할 수 있어 훨씬 편리하다. 

 

---

[백준 7662] 이중 우선 순위 큐

 

TreeMap을 활용하면 쉽게 해결 할 수 있는 문제이다. 

 

 

 

<코드>

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));
        int t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();

            for (int j=0; j<k ;j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                if (command.equals("I")) {
                    if (map.containsKey(num)) map.replace(num, map.get(num) + 1);
                    else map.put(num, 1);
                }
                else if(command.equals("D") && !map.isEmpty()) {
                    if (num == -1) {
                        int key = map.firstKey();
                        if (map.get(key) == 1) {
                            map.pollFirstEntry();
                        }
                        else {
                            map.replace(key, map.get(key)-1);
                        }
                    }
                    else if (num == 1) {
                        int key = map.lastKey();
                        if (map.get(key) == 1) {
                            map.pollLastEntry();
                        }
                        else {
                            map.replace(key, map.get(key)-1);
                        }
                    }
                }
            }

            if (map.isEmpty())  System.out.println("EMPTY");
            else System.out.println(map.lastKey() + " " + map.firstKey());
        }
    }
}

 

 

*) 왜 TreeSet이 아닌 TreeMap을 사용해야 하나?

TreeSet은 중복되는 숫자를 저장하지 않는다.

 

하지만 문제에서 숫자가 중복인 경우 (최솟갑, 최댓값이 2 이상인 경우) 하나만 삭제를 해야한다고 하였는데  TreeSet을 이용하면, 중복되는 모든 값이 사라지는 것과 같은 결과가 나온다. 

 

따라서 TreeMap을 활용하여, Key값은 입력되는 숫자의 값으로 Value 값은 Key값 (숫자)가 몇 개인지를 나타내도록 하면 문제를 해결할 수 있다. 

 

 

 

<출처>

https://dev-coco.tistory.com/39

[Java] TreeMap