no.1764 듣보잡

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

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

    int N, M;
    cin >> N >> M;

    unordered_set<string> noHear;

    for (int i = 0; i < N; i++) {
        string name;
        cin >> name;
        noHear.insert(name);
    }

    vector<string> result;
    result.reserve(M);

    for (int i = 0; i < M; i++) {
        string name;
        cin >> name;
        if (noHear.find(name) != noHear.end()) {
            result.push_back(name);
        }
    }

    sort(result.begin(), result.end());

    cout << result.size() << endl;
    for (auto& name : result) {
        cout << name << endl;
    }

    return 0;
}

 

문제 분석 

1. 듣도 못한 명단을 자료구조에 저장(사이트에서 해시맵으로 분류가 되어 있어 해시맵 사용)

2. 보도 못한 명단을 입력받을 때마다, 이미 드도 못한 명단에 있는지, 확인 

3. 존재하면 교집함으로 간주하여 결과 벡터에 추가

4. 그후 교집합 이름들을 정렬

 

순으로 진행했다.

 

딱히 어려운 점이 없는 문제였다. 

cpp에서 해시맵은 unordered_set이고, 여기에 자료삽입은 insert로 할 수있다.

또한 find의 결과값은 이터레이터로 반환되는데, 이용해 값을 찾았을 때 값이 없다면 end이터레이터가 반환되므로 

if (noHear.find(name) != noHear.end()) {
    result.push_back(name);
}

를 이용하여 결과 벡터에 추가시켜준다. 

 

재미있는점

문제를 풀면서 cpp에서 set과 unoreded_set에 대해 공부했는데, 

일반적으로 unoreded_set은 O(1)에 평균적으로 가까워서

O(logN)인 set보다 빠르게 접근한다고 함. 또한 set은 삽입 시점에 정렬 상태를 유지한다는 것이다.