[c++] 14425 문자열 집합 - Trie (트라이), set, unordered_set

set 과 unordered_set 으로 푸는것이 훨씬 간단한 문제.

set 에 넣고 있는지 비교만 하면된다.

#include <iostream>
#include <string>
#include <set>
#include <unordered_set>
using namespace std;

int N, M, cnt;
string input;
unordered_set<string> s;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        cin >> input;
        s.insert(input);
    }
    for (int i=0; i<M; i++) {
        cin >> input;
        if (s.find(input) != s.end()) {
            cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

 

트라이 자료구조를 이용해서 풀어보았다. 

문자열 찾을 때 자주 사용한다고 한다. 근데 시간이 좀 오래 걸리는듯

 

처음엔 시간초과가 나서 질문검색한 사람들을 찾아보니 string 배열을 통채로 복사되어서 시간초과가 난다고 하길래,

string 배열을 주소값으로 참조하였다.

https://www.acmicpc.net/board/view/48925

 

그리고 80퍼센트 정도에서 틀렸습니다 발생 ! 

또 질문검색에서 발견한 예제

 

5 5
abc
abcd
abcde
abcdef
abcdefg
ab
abc
abcd
abcde
abcdef

 

답: 4

 

원인은 find 함수의 조건문이었다.

여기서 끝났다는 변수 isFinish 과 haveChild 변수와 상관없이,

다음 문자열이 없으면 false를 반환한다.

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define SIZE 26

int N, M;
string input;

struct Trie {
    Trie *next[SIZE];
    bool isFinish;
    bool haveChild;
    
    Trie() {
        fill(next, next + SIZE, nullptr);
        isFinish = haveChild = false;
    }
    ~Trie() {
        for (int i=0; i<SIZE; i++) {
            if (next[i]) {
                delete next[i];
            }
        }
    }
    
    void insert(string &word, int wordSize, int index) {
        if (wordSize <= index) {
            isFinish = true;
            return;
        }
        int wordNum = word.at(index) - 'a';
        if (next[wordNum] == NULL) {
            next[wordNum] = new Trie();
            haveChild = true;
        }
        next[wordNum]->insert(word, wordSize, index + 1);
    }
    
    bool find(string &word, int wordSize, int index) {
        bool result = false;
        if (wordSize <= index) {
            if (isFinish) {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            int wordNum = word.at(index) - 'a';
            if (next[wordNum] == NULL) {
                return false;
            }
            result = next[wordNum]->find(word, wordSize, index + 1);
        }
        return result;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    Trie root;
    for (int i=0; i<N; i++) {
        cin >> input;
        root.insert(input, (int)input.size(), 0);
    }
    int cnt = 0;
    for (int i=0; i<M; i++) {
        cin >> input;
        if (root.find(input, (int)input.size(), 0)){
            cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

 

차례대로 unordered_set, set, trie