23.03.17. 풀었던 문제들

Leetcode 208. Implement Trie (Prefix Tree)

 Trie의 search, insert, startsWith method를 구현하는 문제이다. Trie는 string으로 이루어진 tree이다. 뭐.. 자료구조야 알고 있으니까 넘어가고. 

 

첫 접근

  TrieNode에는 2개의 정보가 있다. 해당 node가 가지고 있는 char 정보인 value, 해당 node가 가지고 있는 childs로의 pointer인 next.

 search나 startsWith 시에는 current node의 childs가 해당 문자를 가지고 있는지 검사하고 없으면 false를 리턴한다. 가지고 있다면 아래로 내려간다. 이 때, startsWith의 경우 문자열의 끝인지 아닌지 상관없이 startsWith string이 존재하기만 하면 되지만 search는 정확하게 그 단어가 있어야 한다. 따라서 문자열 종료를 나타내어 주는 특수문자 0을 넣어준다.

일반적으로 \0을 사용하지만 이미 string에서 문자열 종료 조건으로 이미 \0을 사용하고 있기 때문에 대신 0을 사용했다.

 따라서 insert할 때도 특수문자 0을 덧붙인다.

// Runtime 72 ms Beats 51.10%
// Memory 35.9 MB Beats 93.58%

class TrieNode{
public:
    char value;
    map<char, TrieNode*> next;
};

class Trie {
private:
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        word += "0";
        TrieNode *cur = root;
        for(char c : word){
            if(cur->next.find(c) == cur->next.end()){
                TrieNode *child = new TrieNode();
                child->value = c;
                cur->next[c] = child;
            }
            cur = cur->next[c];
        }
    }
    
    bool search(string word) {
        word += "0";
        return startsWith(word);
    }
    
    bool startsWith(string prefix) {
        TrieNode *cur = root;
        for(char c : prefix){
            if(cur->next.find(c) == cur->next.end()) return false;
            cur = cur->next[c];
        }
        return true;
    }
};

 

 

정석 접근

 일반적으로 각 node에 [isEnd, childs] 2개를 둔다. 위 코드의 경우 char value를 두었는데 굳이 이렇게 할 필요가 없다. 이미 어떤 node로 들어왔다는 것은 그 node의 parent에서 검사하는 char가 있기 때문에 내려온 것이기 때문에 굳이 value를 보관할 필요가 없다. 

 또, 나는 문자열 끝에 0을 덧붙여 거기서 문자열이 종료됨을 알렸는데 이렇게 구현해도 되지만 문자열이 종료되는 경우 isEnd를 이용해 문자열의 끝인지 아닌지 쉽게 확인할 수 있다.

 

// Runtime 74 ms Beats 48.43%
// Memory 33.9 MB Beats 97.6%

class TrieNode{
public:
    map<char, TrieNode*> next;
    bool isEnd; // *** 개선 : isEnd로 단어 종료 여부 판정
};

class Trie {
private:
    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode *cur = root;
        for(char c : word){
            if(cur->next.find(c) == cur->next.end()){
                TrieNode *child = new TrieNode();
                cur->next[c] = child;
            }
            cur = cur->next[c];
        }
        cur->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode *cur = root;
        for(char c : word){
            if(cur->next.find(c) == cur->next.end()) return false;
            cur = cur->next[c];
        }

        return cur->isEnd; // *** 개선 : isEnd로 단어 종료 여부 개선
    }
    
    bool startsWith(string prefix) {
        TrieNode *cur = root;
        for(char c : prefix){
            if(cur->next.find(c) == cur->next.end()) return false;
            cur = cur->next[c];
        }
        return true;
    }
};

 

 

시간복잡도

 insert 시 string의 length만큼 탐색한다. 따라서 O(n)

 search, startsWith 또한 string의 length만큼 탐색한다. 따라서 O(n)

 

공간복잡도

 insert, search, startsWith 시 string length만큼 stack이 쌓인다. 여기서 O(n)

 추가로 모든 string의 char 개수만큼 node가 쌓인다. 각 string의 length를 n, char 개수를 m이라고 하면 O(sum of nm)