[코드트리] Tree Map

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

* 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용.

 

xxilliant 제작

map STL

C++에서는 map이라는 STL을 이용할 수 있습니다.

map은 TreeMap 자료구조로 되어있으며, TreeMap의 경우 균형 잡힌 이진트리 구조로 데이터들을 관리해주는 자료구조 입니다.

 

TreeMap은 각 노드에 (key, value) 쌍 형태로 들어가 있어, key를 기준으로 노드의 위치가 결정되고 각 key에 대한 value값을 저장하는 형태입니다. 따라서 TreeMap에서 모든 함수의 시간복잡도가 전부 O(logN)입니다.

#include <map> 헤더와, map<K, V> name; 형태의 선언이 필요합니다.

또, map은 원래 std::map으로 쓰여야 하므로 using name space std;를 미리 선언합니다.

 

정수를 관리할 map은 다음과 같이 선언해 볼 수 있습니다.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<int, int> m;
    return 0;
}

 

map<int, int> m;로 선언되어 사용될 때를 예로 설명해보겠습니다.

1. m.insert({K, V}) 혹은 m[K] = V

treemap에 쌍(K, V)를 추가합니다.

{K, V}는 실제 std::pair라는 c++에서 제공하는 쌍의 타입입니다. pair는 다음과 같이 이용 가능합니다.

    pair<int, int> p;         // pair형 변수 선언
    p = make_pair(1, 5);      // (1, 5)쌍 선언. p = {1, 5}도 가능
    cout << p.first << endl;  // 첫 번째 값(key) access
    cout << p.second << endl; // 두 번째 값(value) access 

    p.first = 10;             // 첫 번째 값 변경
    p.second = 15;            // 두 번째 값 변경

 

1. m.erase(K)

현재 treemap에 들어있는 데이터 중 key가 K인 쌍을 제거합니다.

1. m.find(K) 혹은 m[K]

현재 treemap에 key가 K인 쌍이 있는지를 확인합니다. m.find(K) 이용시 만약 있다면 해당 iterator를 반환하며, 없다면 m.end()값을 반환합니다. 따라서 값이 있다면 m.find(K) != m.end(), 없다면 m.find(K) == m.end()를 만족할 것입니다.

이때, 원소는 pair 타입이기 때문에 다음과 같이 값에 접근할 수 있습니다.

cout << (m.find(K))->first << endl;     // key가 K인 원소의 key 조회
cout << (m.find(K))->second << endl;    // key가 K인 원소의 value 조회
cout << (*m.find(K)).first << endl;     // key가 K인 원소의 key 조회
cout << (*m.find(K)).second << endl;    // key가 K인 원소의 value 조회

 

값만 조회하고 싶은 경우라면 배열에서 인덱스를 이용하듯이 m[K] 형태로도 이용 가능합니다.

cout << m[K] << endl;                   // key가 K인 원소의 value 조회

 

1. iterator를 이용한 treemap을 key 기준 오름차순으로 순회

 

C++에서는 vector, stack등의 컨테이너들을 iterator라는 반복자를 이용해 순회가 가능하다고 했습니다. 그 중에서도 treemap을 iterator를 이용하여 순회하게 되면, 자동으로 key 기준 오름차순으로 순회가 됩니다.

 

map을 iterator를 이용해 순회하는 코드는 다음과 같습니다.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<int, int> m;            // 정수 쌍을 관리할 treemap을 선언합니다.
    m.insert({5, 6});           
    m.insert({2, 2});           
    m.insert({10, 1});          

    // Iterator를 이용한 map 컨테이너 내의 원소들 순회
    map<int, int>::iterator it;
    // key 기준 오름차순으로 순회하게 되므로
    // (2, 2), (5, 6), (10, 1) 순으로 출력됩니다.
    for(it = m.begin(); it != m.end(); it++) {
        cout << (it -> first) << " " << (it -> second) << endl;
    }    
    return 0;
}

 

만약 순회 전에 map이 비어있는지를 알고싶다면, empty()함수나 size()가 0인지를 확인하면 됩니다.

 

 

출처 코드트리