[백준 14425] 문자열 집합

문제 풀이

 

주어진 문자열 집합 S에서 입력되는 M개의 문자열이 같은 게 몇 개인지를 찾는 문제다.

단순히 생각해보면 전체 집합 S에서 전체 M개의 문자열을 2중 탐색으로 반복해서 문자열 비교까지 하게 된다면

시간 복잡도가 O(10,000 x 10,000 x 500) = 2초를 훌쩍 넘는다.

 

여기서 줄일 수 있는 방법은 문자열 탐색 속도를 줄이는 것이다.

균형 이진 탐색 트리를 사용하는 set이나 map을 이용하게 되면 O(logN) 만에 탐색 속도를 줄일 수 있다.

 

소스 코드

 

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    map<string, bool> m;
    for(int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        m[str] = true;
    }
    
    int cnt = 0;
    for(int i = 0; i < M; i++)
    {
        string str;
        cin >> str;
        if(m[str] == true)
        {
            cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

트라이 이용

 

신기하게도 이 문제는 트라이 자료구조를 이용해서 풀 수 있다.

다만 시간 복잡도가 map은 O(문자열의 개수 10000 x 탐색 시간(log10000))이지만

트라이는 O(문자열의 개수 10000 x 문자열의 길이 500)이므로 여기서는 트라이가 더 느리다.

 

트라이가 항상 빠르다고 생각하면 큰 오산이 되는 문제다.

 

트라이에 문자열 집합 S를 넣어서 완성시키고, 쿼리마다 find 함수를 통해서 등록되어 있으면 카운팅 해주면 된다.

소스 코드(트라이)

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Trie
{
    Trie* ch[26];
    bool end;
    
    Trie() : end(false)
    {
        for(int i = 0; i < 26; i++)
            ch[i] = nullptr;
    }
    
    ~Trie()
    {
        for(int i = 0; i < 26; i++)
            if(ch[i]) delete ch[i];
    }
    
    void insert(const char* str)
    {
        if(!*str)
        {
            end = true;
            return;
        }
        
        int cur = *str - 'a';
        if(!ch[cur]) ch[cur] = new Trie();
        ch[cur]->insert(str + 1);
    }
    
    bool find(const char* str)
    {
        if(!*str)
        {
            if(end) return true;
            return false;
        }
        int cur = *str - 'a';
        if(!ch[cur]) return false;
        return ch[cur]->find(str + 1);
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    Trie* root = new Trie();
    string str;
    for(int i = 0; i < n; i++)
    {
        cin >> str;
        
        root->insert(str.c_str());
    }
    
    int cnt = 0;
    for(int i = 0; i < m; i++)
    {
        cin >> str;
        
        if(root->find(str.c_str()))
        {
            cnt++;
        }
    }
    
    cout << cnt << endl;
    delete root;
    return 0;
}