unordered_map 사용법

#include <unordered_map>

 

map보다 더 빠른 탐색이 가능

해시테이블로 구현한 자료구조

시간복잡도는 O(1)

중복된 데이터를 허용하지 않고

데이터가 많을 시 좋은 성능을 보임.

 

cf) map은 Binary Search Tree

시간 복잡도 O(log n)

 

함수

find(key)

맵에서 key에 해당하는 원소를 찾는 함수

key값이 있으면 iterator를 반환

없으면 map_name.end()

 

count(key)

맵에서 key에 해당하는 원소의 개수를 반환

 

insert({key, value})

맵에 pair<key,value>를 추가하는 함수

key값이 있으면 insert를 하지 않음.

 

erase(key)

맵에서 key에 해당하는 원소를 제거

 

탐색 방법

iterator를 사용하거나

반복문에서는 auto, pair<>

 

unordered_map<string, int> um;
 
 
 
um.insert(make_pair("key", 1));
 
um["banana"] = 2;
 
 
 
// for(auto elem : um)
 
for(pair<string, int> elem : um)
 
       cout << elem.first << elem.second << '\n';
 
 
 
// find 함수 사용법
 
if(um.find("banana") != um.end())
 
         um.erase("banana");

 

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

듣도 못한 사람을 unordered_map에 넣고

보도 못한 사람을 find 해서 듣도 못한 사람에 있으면

듣도 보도 못한 사람.

 

듣보잡의 수와 그 명단을 사전순으로 출력한다.

1. vector에 넣어서 sort() 한다.

2. set()에 넣는다.

 

<소스 코드>

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
string arr[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m;
    cin >> n >> m;
 
    string name;
    unordered_map <string, int> hear;
    set<string> ans;
    
    for (int i = 1; i <= n; i++)
    {
        cin >> name;
        hear[name] = i;
    }
    int cnt = 0;
    
    for (int i = 1; i <= m; i++)
    {
        cin >> name;
        if (hear.find(name) != hear.end())
        {
            cnt++;
            ans.insert(name);
        }
    }
 
    cout << cnt << '\n';
    for (set<string>::iterator it = ans.begin(); it != ans.end(); it++)
    {
        cout << *it << '\n';
    }
}