백준(BOJ)_가희와 키워드(22233번)_C++

처음 문제를 봤을 때 머릿속으로 생각해보면 꽤나 구현이 쉽다고 생각했다.

그냥 문제에 주어진 조건대로 코드를 짜면 됐다.

 

그래서 아래에 있는 정답코드처럼 코드를 짰다.

그런데 시간초과가 나왔다. 시간초과가 나온 코드와 아래의 정답코드의 차이점은 단 하나였다.

바로 시간초과 코드에서는 memo를 set으로 정의했고, 정답코드에서는 unordered_set으로 정의했다는 점이다.

 

set으로 코드를 짰을 때도 시간초과를 염두에 두긴 했다.

그런데 제한 시간이 1.5초였기 때문에 시간초과가 나리라고는 생각하지 않았다.

간단하게 시간복잡도를 계산해보자.

main함수에서 가장 시간복잡도가 큰 곳은 while문이므로 이를 기준으로 시간복잡도를 구해보면

M*(110+10*logN) 이므로 O(M log N) 정도 되는 것 같다.

(혹시 틀렸다면 댓글로 알려주시면 감사하겠습니다.)

때문에 M과 N의 최댓값이 2*10^5 이므로 제한시간 내에 충분히 통과할 줄 알았는데 시간초과가 나왔다.

 

어쨋든 시간초과가 나왔기 때문에 시간복잡도를 줄여야 했다.

근데 내 코드에서 시간복잡도를 줄일만한 곳이 생각나지 않았다.

 

키워드를 파싱하는 부분은 O(110)=>O(1) 이라 줄일 수가 없었고,

그러면 남은 부분은 메모장에서 키워드를 제거하는 부분인데

set에서 데이터를 탐색(제거)하는 부분을 O(log n)보다 더 작은 시간복잡도로 구현할 수 없을 것이라 생각했다.

 

하지만 역시나 그렇듯 답은 존재한다. 바로 자료구조를 바꾸는 것이다.

set 대신 unordered_set을 사용하면 데이터를 탐색하는 부분을 O(log n)에서 O(1)로 줄일 수 있다.

(이것이 가능한 이유는 해쉬 함수를 사용하기 때문인데 더 자세한 내용은 구글에 해쉬 함수를 검색해보자.)

 

알고리즘 수업 때 들었던 내용이 생각났다.

알고리즘의 성능을 개선하는 방법에는 알고리즘 로직, 코드를 수정하는 방법과

더 개선된 자료구조로 변경하는 방법이 있다는 것이다.

 

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int n, m;
unordered_set<string> memo;

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

    cin >> n >> m;

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

    while(m--){
        vector<string> keyword;
        string  s;

        cin >> s;

        //키워드 파싱하기
        string temp="";
        while(s.length()!=0){
            //첫글자가 , 이면 temp를 keyword에 추가하고
            //temp를 빈 문자열로 초기화한 후, 첫글자 제거
            if(s[0]==','){
                keyword.push_back(temp);
                temp="";
                s.erase(s.begin());
            }
            //첫글자가 문자면 첫글자를 temp에 추가하고
            //첫글자 제거
            else{
                temp+=s[0];
                s.erase(s.begin());
            }
        }
        keyword.push_back(temp); //마지막 키워드 추가

        //메모장에서 키워드 제거
        for(int i=0; i<keyword.size(); i++)
            if(memo.find(keyword[i])!=memo.end())
                memo.erase(keyword[i]);

        cout << memo.size() << "\n";
    }
}