[백준] 22233번 가희와 키워드

 

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

22233번: 가희와 키워드

 

시간 1.5초 -> 대충 (n) 2억?으로 생각했다

 

먼저 문제를 읽으면 최대 10개의 키워드에서 Hash_map, map, set 을 써야 하지 않을까 생각했다.
여기서는 자료구조를 생각하는게 중요한 것 같다.

 

글을 쓴 이후 지워진다. -> erase, remove

 

글에 쓴 키워들를 지우고 메모장에 얼만큼에 키워드를 출력 -> 자료구조의 size 출력하면 되겠다라고 생각

 

혹시 시간 시간초과과 된다면 메모장에 있는 키워드를 다 찾았다면, 즉 사이즈가 0이라면 split하는 행위를 멈춰보자.

또한 처음 알게된 사실인데 cout << endl; 이 부분에서 endl이 상당한 시간을 잡아먹기 때문에 << '\n'으로 한다면 이 문제를 해결된다.

처음 endl을 썼을때는 시간초과과 났다. 

 

풀이 코드

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    set<string> key_word;
    long long N, M;
    string str;
    cin >> N >> M;


    for (long long i = 0; i < N; i++) {
        cin >> str;
        key_word.insert(str);
    }

    for (long long j = 0; j < M; j++) {
        string word;
        cin >> str;
        str += ',';
        long long start = 0;
        long long i = 0;
        if (key_word.size() != 0) {
            while (true) {
                start = str.find(',');
                word = str.substr(0, start);

                key_word.erase(word);

                if (start == str.length() - 1) {
                    break;
                }

                i = start + 1;
                str = str.substr(i, str.length());
            }
        }
        cout << key_word.size() << '\n';
    }
}