22233 - 가희와 키워드

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

22233번: 가희와 키워드

생각해 보기

• 단순 list나 vector의 경우 시간제한이 굉장히 빡빡하다.
• set혹은 map을 사용하자.
• c++의 경우 ,를 가지고 split하는 istringstream을 사용할 수 있다. #include<sstream>을 추가하자

코드

#include<iostream>
#include<unordered_set>
#include<sstream>

using namespace std;

int N,M;
unordered_set<string> words;

void input(){
    cin>>N>>M;
    string word;
    while(N--){
        cin>>word;
        words.insert(word);
    }
}

void solution(){
    string used;
    while(M--){
        cin>>used;
        istringstream ss(used);
        string buffer;

        while(getline(ss, buffer, ',')){
            if(words.find(buffer) == words.end())
                continue;

            words.erase(words.find(buffer));
        }
        cout<<words.size()<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}

unordered_set과 set의 시간 차이가 2배 가량 났다.

insert와 delete의 시간차이가 find로 인해 늘어나는 시간보다 훨씬 긴걸로 추측된다.