C++ 맵(map) 사용법 (BOJ 17219)

map 컨테이너에 대하여

벡터(vector)와 마찬가지로 C++의 표준 라이브러리에 내장된 컨테이너의 일종이다. key와 value라는 값이 페어(pair)로서 한 쌍을 이루는 것이 특징이며, key 값은 중복을 허용하지 않는다. 값을 저장할 때마다 map 내부의 값들은 key를 기준으로 자동으로 오름차순 정렬된다. 자료구조는 레드 블랙 트리(이진 탐색 트리)로 구현되어 있어, 최고 O(log N)의 시간 복잡도를 지닌다고 한다. (트리에 대한 자세한 내용은 추후에 다른 포스팅에서 다루어보려 한다.)

• map <자료형1, 자료형2> m1; → 자료형1에 해당하는 key 값과 자료형2에 해당하는 value 값을 저장할 수 있는 맵 m1을 선언한다.

• m1.insert({key값, value값}); → 페어 {key값, value값}을 맵 m1에 저장한다. (이 때, 해당 페어는 맵 m1에 자동으로 오름차순 정렬되어 저장된다.)

• m1.begin() → 맵 m1의 맨 앞에 있는 요소

• m1.end() → 맵 m1의 맨 뒤에 있는 요소의 바로 뒤

• m1.erase(key값); → 해당 key 값에 해당하는 페어를 맵 m1에서 찾아 삭제한다.

• m1.erase(위치); → 해당 위치에 있는 페어를 맵 m1에서 삭제한다. (이 때, 특정 위치는 m.begin()+n (n은 정수), 특정 범위는 **m.begin(), m.end()**와 같은 형태로 작성한다.)

• m1.clear(); → 맵 m1의 모든 요소들을 삭제한다.

• m1.find(key값) → 해당 key 값에 해당하는 페어가 있는지 찾는다. 없으면 m1.end()를 반환한다.

• m1.find(key값)->first → 해당 key 값에 해당하는 페어의 key 값

• m1.find(key값)->second → 해당 key 값에 해당하는 페어의 value 값

다음은 BOJ의 몇몇 문제들을 벡터와 페어를 이용한 풀이들이다.

boj_17219 (2022. 12. 13. 풀이)

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

string s, s2;
map <string, string> m1;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n >> m;
    cin.ignore();
    for (int i=0; i<n; i++) {
        getline(cin, s, ' ');
        getline(cin, s2);
        m1.insert({s, s2});
    }

    for (int i=0; i<m; i++) {
        cin >> s;
        cout << m1.find(s)->second << "\n";
    }
}