Tutorial : STL Map 1 ( 기본 개념 ) timer 2s memory 1024MB

STL Pair 자료형을 공부하고 왔으니, 이제는 STL map 자료구조를 배우자.

아래 코드를 보자.

arr[1] = 1;
arr[1000000000] = 1;

arr 배열의 1번 칸과, 10억번 칸에 1 을 집어넣는 단순한 코드다.

하지만, 만약 이를 원래 쓰던 1차원 배열로 구현하면 어떤 문제점이 생길까?

a[1000000000] = 1 을 하기 위해서는, 배열 a 의 크기가 10억 보다 커야 한다.

10억 개의 어마어마한 양의 칸을 만들어도, 정작 쓰이는 칸은 a[1] 과 a[1000000000] 두 곳 밖에 없다...

이 얼마나 비효율적인가!

이를 해결하기 위한 방법 중 하나가 STL map 이다.

STL Map 은, 위의 예시처럼, 집어 넣는 원소 개수는 적은데, 그 범위가 매우 클 때 유용하다.

( 위의 예시도, 집어 넣는 원소 개수는 2개 뿐인데, 원소 범위가 무려 10억이다. )

map 은 Pair 형태로 자료를 저장한다. #include <map> 헤더에 존재한다.

선언 법은 아래와 같다.

#include <map>
using namespace std;

map <int, int> m; // pair <int, int> 를 저장하는 자료구조

위처럼 map <자료형, 자료형> 이름; 으로 선언해주면 된다.

이렇게 map <int, int> m; 으로 선언한 경우,

m 은 pair<int, int>, 즉 ( 정수, 정수 ) 순서 쌍을 담을 수 있게 된다.

이제, map 안에 순서 쌍을 넣는 법을 알아보자.

대표적으로 2가지 방법이 있다.

{100, 200} 순서 쌍을 넣고 싶다면 아래처럼 짜면 된다.

map <int, int> m;

m[100] = 200; // <방법 1>
m.insert ( {100, 200} ); // 방법 2

<방법 1>, <방법 2> 모두 맞는 방법이다. 두 방법 모두, {100, 200} 순서 쌍이 m 안에 들어가게 된다.

주로 <방법 1> 이 조금 더 많이 쓰이긴 한다.

여기서 주의할 점은, m[100] = 200 은 m 의 100번째 칸에 200을 넣는 작업이 아니라는 것 이다.

m[100] = 200 은, {100, 200} 이라는 순서 쌍을 m 에 추가하는 작업이다.

Map 을 1차원 배열과 헷갈리면 안 된다.

1차원 배열에서 m[100] = 200 을 하려면, m[0] ~ m[99] 까지 100칸 메모리를 쓸데없이 만들어야 하지만,

map 에서 m[100] = 200 을 하면, {100, 200} 순서 쌍 하나의 메모리만 만들어진다.

메모리를 굉장히 많이 아끼게 된 것이다!

map 에 들어가는 Pair 에서, 앞 원소(first) 를 key, 뒤 원소(second) 를 value 라고 부른다.

즉, m 에 삽입되는 순서 쌍 {100, 200} 에서, key = 100 이고 value = 200 이 되는 것이다.

이번엔 아래와 같은 코드를 보자.

map <int, int> m;

m[5] = 8;  // {5, 8} 순서 쌍이 추가됨
m[5] = 2;  // {5, 8} 순서 쌍이 {5, 2} 로 바뀐다.
m[7] = 9;  // {7, 9} 순서 쌍이 추가됨

처음에는 {5, 8} 순서 쌍이 m 에 추가된다.

이후 {5, 2} 순서 쌍이 하나 더 들어가는 게 아니고, {5, 8} 순서 쌍이 {5, 2} 로 바뀐다.

즉, 한 key 값 당 value 는 하나만 가능하다.

이후 {7, 9} 순서 쌍이 새롭게 삽입된다.

이를 한눈에 본 그림이 아래와 같다.

마지막으로 Map 의 중요한 성질을 보자. 바로 실시간 정렬이다.

Map 의 원소들은 key 를 기준으로 (pair 의 first 값을 기준으로) 실시간으로 정렬된다.

아래 코드를 보자. 순서 쌍 5개를 삽입하는 상황이다.

 #include <map>
using namespace std;

int main(){
    map <int, int> m;

    m[2] = 3;
    m[-2] = 1;
    m[5] = 3;
    m[1] = 4;
    m[2] = 8;
}

각 줄이 실행될 때마다, key 를 기준으로 순서 쌍들이 자동 정렬된다.

이것도 아래 그림을 보면 바로 원리가 이해 갈 것이다.

각 순서 쌍이 삽입될 때마다, Map 은 이들을 key 값을 기준으로, 실시간 정렬을 한다.

순서 쌍들의 key 값(앞 숫자) 를 보면, 항상 정렬이 되어 있음을 볼 수 있다.

따라서 Map 에서 원소를 삽입하고 검색하는 모든 과정은 O(log N) 의 시간이 추가로 걸린다.

Map 의 모든 원소를 순서대로 출력하려면 어떻게 하면 될까?

Map 은 Pair 들을 담는 자료구조이기에,

auto 를 활용한 range-based for문을 활용하면 된다.

따라서 아래와 같이 2가지 방법이 있다.

물론 이 외에도 몇 가지 방법이 더 있다.

아래 2가지 방법이 이해가 가지 않으면 반드시 auto 를 활용한 range-based for문을 다시 공부하고 오자.

map <int, int> m;

// 방법 1 : 단일 변수 element
for(auto element : m){
    printf("%d %d\n", element.first, element.second);
}

// 방법 2 : 변수 분리 [key, value]
for(auto [key, value] : m){
    printf("%d %d\n", key, value);
}

※ 참고 : 만약에 순서 쌍을 map 에서 제거하고 싶다면?

erase() 함수를 사용하면 된다.

위 그림에서 {2, 8} 을 제거하고 싶다면, key 값인 2 만 넣어주면 된다.

m.erase(2);

만약 m.erase(7) 을 한다면?

key 값이 7 인 순서 쌍은 원래 없었다. 따라서 아무 일도 일어나지 않는다. (오류가 발생하진 않는다.)

< 응용 문제 >

사람들의 이름이 영어 소문자들로만 이루어진 문자열로 주어진다. ( 각 이름은 최대 50자다. )

입력을 끝마친 후, 각 이름들이 몇 번째 줄에서 마지막으로 입력됐는지, 사전 순으로 정렬하여 출력하는 프로그램을 작성하여라.