백준 / 14425 / C++ [unordered, map, set]

실행시간이 동일했다.

map, set은 tree 구조를 가져 최선 O(logN) ~ 최악 O(logN) 복잡도를 가진다
unordered_map, unordered_set은 둘 다 hash를 사용하여 최선 O(1) ~ 최악 O(N) 복잡도를 가진다.

unordered_set :

s.insert(e)

s.find(e) != s.end()

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, i, a=0;
    string s;
    unordered_set<string> strs;
    cin >> n >> m;
    
    for (i=0; i<n; i++) {
        cin >> s;
        strs.insert(s);
    }
    for (i=0; i<m; i++) {
        cin >> s;
        if(strs.find(s) != strs.end())
            a++;
    }
    cout << a;
}

unordered_map

um[k] = v;

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, i, a=0;
    string s;
    cin >> n >> m;
    unordered_map<string, bool> u(n);
    
    for (i=0;i<n;i++){
        cin >> s;
        u[s] = true; //u.insert(pair<string, bool>(s, true));
    }
    for (i=0;i<m;i++){
        cin >> s;
        if (u[s]) a++;
    }
    cout << a;
}

주의: u[s]가 존재하지 않으면 default로 새로 삽입한다.

Defaults

• bool: false
• int, double: 0 등

https://modoocode.com/224