[자료구조/C++] 맵(map)

[ 1 ] 기본내용

map은 기본적으로 entry라고 불리는 (key, value)쌍이 저장되는 자료구조이다. 하나의 map은 중복된 key값을 가질 수 없다는 특성과 key값으로 해당 key값과 mapping된 value를 쉽게 검색할 수 있는 특성으로 인해 정보 저장 및 검색에 유리한 자료구조이다.

 

대표적인 map의 특성은 다음과 같다.

- map은 중복된 key값을 가질 수 없기 때문에 하나의 key가 여러 개의 value값을 가질 수 없다.

- map의 주요 연산으로는 search, insert, erase가 있다.

- map을 연결리스트로 구현할 경우 위의 주요 연산의 시간복잡도는 O(n)이다.

- map 연산의 시간복잡도를 줄이기 위해 hash map 등을 활용하기도 한다.

 

[ 2 ] C++에서의 map

[2 - 1] 헤더파일

C++에서는 map 자료구조를 제공하고 있으며, 트리의 높이를 O(log n)으로 유지하는 트리 자료구조 중 하나인 Red-Black tree로 구현되어 있다. 그러므로 C++ map 관련 연산의 시간복잡도는 O(log n)을 보장받는다. map을 사용하기 위해서는 우선 map 헤더파일을 include 한다.

 

#include <map>

 

[2 - 2] 멤버함수

C++에서 제공하는 map의 멤버함수는 다음과 같다(자주 사용하는 멤버함수 위주로 정리했다).

멤버함수	내용
find(k)	k는 key값이며, key를 가리키는 반복자를 반환한다. key값이 map에 없다면 m.end()와 같은 반복자를 반환한다.
insert(k) insert(iter, k)	key를 삽입하는데, C++의 map은 기본적으로 key를 기준으로 오름차순으로 정렬되기 때문에 insert시 자동으로 정렬된 위치에 key값이 삽입된다. insert(iter, k)는 iter가 가리키는 위치부터 k를 삽입할 위치를 탐색한 후 k를 삽입한다. ※ 단, map에는 기본적으로 (key, value) 쌍이 저장되므로 k는 pair 객체이다.
erase(iter) erase(start, end)	iter가 가리키는 map의 원소를 삭제한다. erase(start, end)의 경우 start부터 end-1까지의 원소를 모두 삭제한다.
size()	map에 저장된 원소의 개수를 반환한다.
empty()	map이 비었다면 true를, 그렇지 않다면 false를 반환한다.

 

[2 - 3] 기본 형태 및 기본 예제

map의 기본 형태는 다음과 같다.

- map<key type, value type> map_name;

 

C++의 map은 기본적으로 key를 기준으로 오름차순으로 정렬된다. 따라서 내림차순으로 정렬하려면 

- map<key type, value type,  greater> map_name; 

로 선언하면 된다.

 

물론 key값을 기준으로 map을 정렬할 필요가 없을수도 있고, 연산의 더 빠른 시간복잡도를 보장받기 위해 정렬되지 않은 map을 선언할 수도 있다. 이를 사용하기 위해서는 #include <unordered_map> 헤더파일을 포함해야 한다.

- unordered_map<key type, value type> map_name;

로 선언하면 된다.

 

앞에서 언급했듯이 C++의 map은 Red-Black tree로 구현되었기 때문에 원소가 정렬되고, O(log n)의 시간복잡도를 가진다. 하지만, unordered_map은 hash table로 구현되기 때문에 시간복잡도를 O(1)로 줄일 수 있다. 즉, 방대한 데이터를 저장할 때는 map보다 unordered_map이 훨씬 좋은 성능을 보인다.

 

 

 (1) 삽입예제

#include <map>

using namespace std;

int main(void)
{
    map<int, int> m;
    
    m.insert(pair<int, int> (1, 100));
    m.insert(pair<int, int> (2, 2000));
    m[3] = 3000;
    
    return 0;
}

insert에는 두 가지 방법이 있다. 첫 번째는 insert 멤버함수를 활용하여 pair객체를 직접 넣어주는 방법이고, 두 번째는 m[key] = value; 로 원소를 삽입하는 방법이다. 두 방법모두 동일하게 동작한다.

 

 (2) 탐색예제

auto it = m.find(1);
if(it != m.end())
{
    cout << "find: " << it->first << " " << it->second << endl;
}
else
{
    cout << "not find" << endl;
}

위에서 언급했듯이 멤버 함수 find(k)는 k 발견 시 k를 가리키는 반복자를, k 발견하지 못했을 시 m.end()와 같은 반복자를 반환한다. 그러므로 위와 같이 k를 탐색할 수 있다.

k를 발견했을 때 반복자를 통해 key값과 value값에 접근할 수 있는데, it->first는 key 값을, it->second는 value 값을 의미한다.

 

 (3) 삭제예제

m.erase(iter) 멤버함수와 m.erase(key)로 해당 (key, value) entry를 삭제할 수 있고, m.erase(m.begin(), m.end())로 map의 모든 원소를 삭제할 수 있다.

// 두 번째 원소 삭제
m.erase(m.begin()+1);

// key값이 1인 원소 삭제
m.erase(1);

// map의 모든 원소 삭제
m.erase(m.begin(), m.end());

 

(4) 순회예제

for(auto it = m.begin(); it != m.end(); it++)
{
    cout << "[" << it->first << ", " << it->second << "]" << endl;
}

다음과 같이 반복자로 map의 모든 원소를 순회할 수 있으며, first와 second를 통해 (key, value) 값에도 접근할 수 있다.

 

[ 3 ] map 활용 문제 - 백준

문제출처: https://www.acmicpc.net/problem/1620

1620번: 나는야 포켓몬 마스터 이다솜

백준 '단계별로 풀어보기'의 '집합과 맵'파트에서 map 활용 문제들을 풀어보자. 위 문제는 특히 "시간 초과"를 유의하며 해결해야 하는 문제이다!

 

(풀이는 향후 업로드 예정)