[C++ STL] map<K, V> 사용 방법 | 백준 7785번, 1764번

map<K, V> 란?

AVL 트리의 자료구조로 구현된 C++ STL을 의미한다.

 

먼저, AVL 트리(균형잡힌 이진탐색트리)란 balanced Binary Search Tree를 만족하면서 Height-balance property를 만족하는 자료구조를 의미한다.

 

이때, Height-balance property란 임의의 노드 v에 대하여 v의 두 자식의 height 차이가 많아야 1인 property를 말한다.

 

따라서, AVL 트리는 항상 트리의 높이가 점근적으로 O(logN)에 바운드가 되므로, 이 자료구조의 삽입, 삭제, 탐색 등 모든 연산의 시간 복잡도는 O(logN)을 보장한다.

 

map<K, V>의 include 방법

#include <map>

다음과 같이 map의 헤더를 include하면 사용할 수 있다.

주요 메서드

주요 메서드를 설명하기 전, 아래 코드를 기준으로 설명하겠다.

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    map<int, int> m;
    return 0;
}

삽입 메서드(insert)

m.insert({K, V})로 Map에 키가 K이고 값이 V인 entry를 삽입(추가)할 수 있다.

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    map<int, int> m;
    //삽입 메서드
    m.insert({5, 2});
    m.insert({3,10});
    m.insert({1,7});
    m.insert({4,2});
    m.insert({2,5});

    return 0;
}

삭제 메서드(erase)

m.erase(K)로 현재 Map에 키가 K인 entry가 존재한다면 삭제한다.

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    map<int, int> m;
    //삽입 메서드
    m.insert({5, 2});
    m.insert({3,10});
    m.insert({1,7});
    m.insert({4,2});
    m.insert({2,5});

    //삭제 메서드
    m.erase(1);
    m.erase(4);
    
    return 0;
}

탐색 메서드(find)

m.find(K)로 현재 Map에 키가 K인 entry가 존재한다면 해당 entry의 iterator를 리턴하고, 존재하지 않는다면 m.end()를 리턴한다.

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    map<int, int> m;
    //삽입 메서드
    m.insert({5, 2});
    m.insert({3,10});
    m.insert({1,7});
    m.insert({4,2});
    m.insert({2,5});

    //삭제 메서드
    m.erase(1);
    m.erase(4);

    //탐색 메서드
    if(m.find(5) != m.end()) {
        cout << "existed" << endl; // existed
    } else {
        cout << "not existed" << endl;
    }
    
    return 0;
}

보조 메서드

map의 iterator 순회 | key를 기준으로 오름차순으로 순회한다.

다음 코드와 같이 iterator의 타입은 map의 타입과 동일하게 선언한 뒤 for문을 통해 map을 key를 기준으로 오름차순 순회할 수가 있다.

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    map<int, int> m;

    m.insert({5, 2});
    m.insert({3,10});
    m.insert({1,7});
    m.insert({4,2});
    m.insert({2,5});

    map<int, int>::iterator it;
    for(it = m.begin(); it != m.end(); it++) {
        cout << it->first << " " << it->second << endl;
    }
    
    return 0;
}

출력 결과

---

map을 사용한 대표적인 관련 백준 문제 | C++

7785번 회사에 있는 사람

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    map<string, string, greater<string>> m;
    for(int i{ 0 }; i < n; i++) {
        string user, log;
        cin >> user >> log;
        if(log == "enter") {
            m.insert({user, log});
        } else {
            m.erase(user);
        }
    }
    for(map<string, string, greater<string>>::iterator it = m.begin(); it != m.end(); it++) {
        printf("%s\n", it->first.c_str());
    }
    return 0;
}

map은 다음 문제와 같이 삽입과 삭제 연산에 있어서 항상 O(logN)을 보장하므로 효율적이며, Key를 기준으로 오름차순 또는 내림차순 정렬을 iterator로 순회할 수 있으므로 출력에 유리하다.

 

따라서, map 자료구조는 삽입, 삭제의 연산이 빈번한 문제 상황과 해당 데이터를 오름차순 또는 내림차순 접근이 필요한 상황에 사용하면 된다.

---

1764번 듣보잡

#include <iostream>
#include <map>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    map<string, bool> sm;
    for(int i{ 0 }; i < n; i++) {
        string s;
        cin >> s;
        sm.insert({s, false});
    }
    int size = 0;
    for(int i{ 0 }; i < m; i++) {
        string s;
        cin >> s;
        if(sm.find(s) != sm.end()) {
            sm[s] = true;
            size++;
        }
    }
    printf("%d\n", size);
    for(map<string, bool>::iterator it = sm.begin(); it != sm.end(); it++) {
        if(it->second) {
            printf("%s\n", it->first.c_str());
        }
    }
    return 0;
}

1764번도 삽입과 탐색이 빈번하게 일어나고 마지막에 사전순(오름차순) 출력을 요구하는 문제이다.

따라서, map 자료구조를 사용하면 효율적으로 사전순으로 출력할 수가 있다.