들어가며
- 해당 시리즈는 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet에서 이어진다.
- 이번엔 Associative Containers의 종류 중 하나인 TreeMap에 대하여 알아볼 것이다.
2023.01.15 - [Algorithm/Before Check] - Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet
Map의 정의
- TreeSet을 알아보기 이전에 Set에 대하여 알아본 것 처럼 TreeMap을 이해하기 위해서는 Map에 대한 선행지식이 요구된다. 따라서 Map에 대하여 간략하게 알아보자.
- Map <Key, Value>로 이루어진 한 쌍이 하나의 요소로 이 요소들로 이루어진 자료구조가 Map이다. 이 구조와 이에 필요한 연산을 정의한 것이 Map 인터페이스이다. Python을 한 적이 있는 사람이라면 딕셔너리가 이 Map이라고 할 수 있겠다.
- Map에서 Key와 Value는 다음의 특징을 가진다.
- Key는 해당 Map에서 유일하게 존재해야한다. 즉, 중복된 key가 Map에 존재해선 안된다.
- Value는 해당 Map에서 유일하게 존재하지 않아도 된다. 즉, 중복된 Value가 서로 다른 Key에 존재할 수 있다.
- C++에선 Key의 중복을 허용하는 std::multimap, std::multiset이 존재하나 Java는 자체적으로는 아직 존재하지 않고 google의 패키지에서 지원하는 구조가 있는 것으로 알고있다.
- Java에서 바로 <Key, Value>쌍을 표현하기는 어렵기 때문에 Map의 내부요소들은 Map.Entry<>라는 인터페이스로 감싸지는 방식으로 <Key, Value>쌍을 표현하였다.
TreeMap의 정의
- TreeMap은 이전에 TreeSet을 본 사람은 유추할 수 있겠지만 이진 검색 트리를 사용한 Map이다. 정렬되어 있고, 정렬된 순서를 유지한다는 것이 Map과의 차이점이다.
- 동일하게 이진 검색 트리를 사용한 자료구조이기 때문에 연산 메서드의 이름도 비슷한 것들이 많다. TreeMap의 연산 종류는 다음과 같다.
메서드 | 메서드 타입 | 설명 |
TreeMap() | constructor | TreeMap 객체를 반환한다. |
TreeMap(Comparator comp) | constructor | 지정된 비교방법으로 정렬하는 TreeMap 객체를 반환한다. |
TreeMap(Map m) | constructor | Map의 모든 요소를 포함하고 있는 정렬된 TreeMap객체를 반환한다. |
ceilingEntry(K k) | Map.Entry<K, V> | 지정된 키보다 크거나 같은 요소들 중 가장 가까운 엔트리를 반환한다. |
ceilingKey(K k) | K | 지정된 키보다 크거나 같은 요소들 중 가장 가까운 엔트리의 키를 반환한다. |
comparator() | Comparator<> | TreeMap이 현재 사용하는 Comparator 객체를 반환한다. |
containsKey(Object key) | boolean | 지정된 키가 TreeMap에 존재하는지 확인한다. |
containsValue(Object val) | boolean | 지정된 값이 TreeMap에 존재하는지 확인한다. |
descendingKeySet() | NavigableSet<K> | TreeMap을 역순으로 정렬한 결과를 Set으로 반환한다. |
descendingMap() | NavigableMap<K, V> | TreeMap을 역순으로 정렬한 결과를 Map으로 반환한다. |
entrySet() | Set<Map.Entry<K, V>> | TreeMap의 모든 요소를 Set으로 변환하여 반환한다. TreeMap의 특성상 정순정렬한 결과를 반환하게 된다, |
firstEntry() | Map.Entry<K, V> | TreeMap의 첫 번째 엔트리를 반환한다. |
firstKey() | K | TreeMap의 첫 번째 엔트리의 키를 반환한다. |
floorEntry(K k) | Map.Entry<K, V> | 지정된 키보다 작거나 같은 요소들 중 가장 가까운 엔트리를 반환한다. |
floorKey(K k) | K | 지정된 키보다 작거나 같은 요소들 중 가장 가까운 엔트리의 키를 반환한다. |
get(Object key) | V | 지정된 키에 존재하는 값을 가져온다. |
headMap(K toKey) | SortedMap<K, V> | 지정된 키보다 작은 키를 가진 요소들의 Map을 반환한다. |
headMap(K toKey, boolean inclusive) | NavigableMap<K, V> | 지정된 키보다 작은 키를 가진 요소들의 Map을 반환한다. Inclusive가 true라면 지정된 키도 포함된다. |
higherEntry(K key) | Map.Entry<K, V> | 지정된 키보다 큰 키의 엔트리 중 가장 가까운 엔트리를 반환한다. 존재하지 않을 시 null을 반환한다. |
higherKey(K key) | K | 지정된 키보다 큰 키의 엔트리 중 가장 가까운 엔트리의 키를 반환한다. 존재하지 않을 시 null을 반환한다. |
keySet() | Set<K> | TreeMap의 모든 키를 Set으로 반환한다. |
lastEntry() | Map.Entry<K, V> | TreeMap의 마지막 엔트리를 반환한다. |
lastKey() | K | TreeMap의 마지막 엔트리의 키를 반환한다. |
lowerEntry(K key) | Map.Entry<K, V> | 지정된 키보다 작은 키들 중 가장 가까운 키의 엔트리를 반환한다. |
lowerKey(K key) | K | 지정된 키보다 작은 키들 중 가장 가까운 키를 반환한다. |
put(K key, V value) | V | TreeMap에 <key, value>를 삽입한다. |
putAll(Map m) | void | 지정된 Map의 모든 요소를 TreeMap에 삽입한다. |
remove(Object key) | V | TreeMap에 지정된 key의 <key, value>를 삭제한다. |
replace(K key, V value) | V | TreeMap에 지정된 key의 값을 value로 재지정한다. |
replace(K key V oldVal, V newVal) | boolean | TreeMap에 지정된 key와 oldVal이 동일한 요소의 값을 newVal로 재지정한다. |
subMap(K fromKey boolean fromInclusive, K toKey, boolean toInclusive) | NavigableMap<K, V> | fromKey부터 toKey사이의 요소들을 Map으로 담아 반환한다. 각 inclusive가 true이면 각 요소들도 포함된다. |
subMap(K fromKey, K toKey) | SortedMap<K, V> | fromKey부터 toKey사이의 요소들을 Map으로 담아 반환한다. fromKey는 포함되고 toKey는 포함되지 않는다. |
tailMap(K fromKey) | SortedMap<K, V> | fromKey보다 큰 요소들을 담아 Map으로 반환한다. |
tailMap(K fromKey, boolean inclusive) | NavigableMap<K, V> | fromKey보다 큰 요소들을 담아 Map으로 반환한다. Inclusive가 true이면 fromKey도 포함된다. |
values() | Collection<V> | TreeMap내의 모든 값을 Collection으로 반환한다. |
pollFirstEntry() | Map.Entry<K, V> | TreeMap의 처음 엔트리를 제거하고 그 엔트리를 반환한다. |
pollLastEntry() | Map.Entry<K, V> | TreeMap의 마지막 엔트리를 제거하고 그 엔트리를 반환한다. |
'Algorithm > Before Check' 카테고리의 다른 글
Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet (0) | 2023.01.15 |
---|---|
Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - LinkedList (1) | 2023.01.15 |
Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - ArrayList, Deque (0) | 2023.01.15 |