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

 

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

22233번: 가희와 키워드

 

키워드는 모두 서로 다르고, 총 N개 존재

최대 10개의 키워드에 대해서 글을 작성

글을 쓰면 해당 키워드는 메모장에서 지워진다

블로그에 글을 쓰고 나서 메모장에 있는 키워드 개수가 몇 개인지 알고 싶다.

 

처음엔 그냥 vector로 했다가 중복 제거하는 set으로 바꿨다가

계속 시간 초과가 발생해서 뭐지 했는데 unordered_set으로 하면 됐다!!!!

이름만 들어도 set보다 시간이 덜 걸릴거 같은...!

unordered_set은 정렬하지 않고 삽입한 순서대로 내버려둔다.

 

, 위치를 찾아서 이를 기준으로 substr를 만들고 unordered_set에서 있는지 없는지 find 함수를 통해서 진행했다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_set>
#define MAX 200001
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;       //n: 키워드 개수, m: 글 개수
    string keyword;
    unordered_set<string> us;
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> keyword;
        us.insert(keyword);
    }
    while(m--){
        string posting;
        cin >> posting;
        int pos = 0;
        while(pos<posting.size()){
            auto it = posting.find(',', pos); //pos 위치부터 시작해서 , 위치 찾기
            if(it == posting.npos){           //만약 , 없다면 (마지막 키워드)
                string sub = posting.substr(pos); //pos부터 끝까지 sub string
                if(us.find(sub) != us.end()) us.erase(sub); //us에 sub 키워드가 있다면 지우기
                break;
            }else{ //만약 , 있다면
                string sub = posting.substr(pos, it-pos);   //pos부터 ,직전까지 sub string
                if(us.find(sub) != us.end()) us.erase(sub); //us에 sub 키워드가 있다면 지우기
                pos = it + 1; //, 다음위치로 업데이트
            }
        }
        cout << us.size() << '\n';
    }
    return 0;
}