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

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

22233번: 가희와 키워드

해시를 이용할 때 ordered_set이 아니라 unordered_set을 이용해야 한다.

unorded_set은 set과 다르게 정렬되지 않으며 해시 함수를 이용해 원소를 탐색한다.

Set은 정렬되어있는 상태에서 탐색을 하므로 $O(log N)$ 시간이 걸린다. 평균도 최악도!

Hash Set은 해시 함수로 탐색을 하므로 평균 $O(1)$ 상수 시간이 걸려 빠르지만 해시 충돌도 고려를 해야 하고, 해시 충돌이 많은 경우에는 Set이 더 효율적이다.

 

참고로 앞에 입출력 동기화를 풀어줘야 시간 초과가 발생하지 않는다.

#include <iostream>
#include <unordered_set>
using namespace std;
int n, m;
void parse_keyword(string memo, unordered_set<string> &keywords) {
    while(auto pos = memo.find(",")) {
        if(pos == string::npos) {
            break;
        }
        string keyword = memo.substr(0, pos);
        keywords.erase(keyword);
        memo = memo.substr(pos + 1);
    }
    keywords.erase(memo);
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    string str, memo;
    unordered_set<string> keywords;
    
    for(int i = 0;i < n;i++) {
        cin >> str;
        keywords.insert(str);
    }
    
    for(int i = 0;i < m;i++) {
        cin >> memo;
        parse_keyword(memo, keywords);
        cout << keywords.size() << '\n';
    }
}