(매일 BOJ) C++ 1764번 듣보잡

이번 문제는 1764번 듣보잡이다.

접근법

• 두 리스트의 교집합을 구해야 함
• 각 이름은 문자열이며 중복되지 않음
• 이름이 50만 개씩 들어오므로 시간복잡도 O(N log N) 이하 알고리즘 필수

작성코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    long long N,M;
    cin >> N >> M;
    unordered_set<string> s;

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

    vector<string> v;
    long long count = 0;

    for(int j = 0; j < M; j++){
        string str;
        cin >> str;
        auto a = s.count(str);
        if (a){
            v.push_back(str);
            count += 1;
        } 
    }
    sort(v.begin(),v.end());
    cout << count << '\n';
    for(string s : v){
            cout << s << '\n';
    }    
}