23.03.19. 풀었던 문제들

Leetcode 211. Design Add and Search Words Data Structure

 먼젓번 풀었던 Leetcode 208. Implement Trie처럼 trie를 구현하는 문제이다. 단 .이라는 wildcard가 추가되어 이에 대한 로직을 작성해야 한다. 기본적인 trie의 로직은 저번에 풀었던 문제와 동일하므로 넘기고 .에 대해 어떻게 처리했는지만 서술하려 한다.

 

• 만약 [현재 탐색중인 char]이 .이 아니라면 trie 탐색하는 것처럼 탐색한다.
• [현재 탐색중인 char]이 .이라면 [현재 탐색중인 TrieNode의 모든 child]를 탐색해야 한다. 따라서 DFS를 사용한다. 
  • DFS를 위해 searchHelper function을 만들고 현재 탐색중인 word 다음 것부터 복사해 같은 탐색을 진행한다.

// Runtime 2398 ms Beats 13.14%
// Memory 349.3 MB Beats 92.50%

class TrieNode{
public:
    bool isEnd;
    map<char, TrieNode*> childs;
};

class WordDictionary {
public:
    TrieNode *root;

    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode *cur = root;
        for(char c : word){
            if(cur->childs.find(c) == cur->childs.end()){
                TrieNode *next = new TrieNode();
                cur->childs[c] = next;
            }
            cur = cur->childs[c];
        }
        cur->isEnd = true;
    }

    bool searchHelper(string word, TrieNode *cur){
        for(int i = 0; i<word.size(); i++){
            if(word[i] != '.'){
                if(cur->childs.find(word[i]) == cur->childs.end()) return false;
                cur = cur->childs[word[i]];
            }
            else{ // wildcard인 경우 cur의 모든 child 재귀 탐색
                for(auto [key, value] : cur->childs){
                    if(searchHelper(word.substr(i+1), value)) return true;
                }
                return false;
            }
        }
        if(cur->isEnd) return true;
        else return false;
    }
    
    bool search(string word) {
        return searchHelper(word, root);
    }
};

 

시간복잡도

 insert 시 string의 length만큼 탐색한다. 따라서 O(n)
 search시 .이 없는 경우 또한 string의 length만큼 탐색하므로 O(n). 단 wildcard가 있는 경우에는 모든 child를 탐색하게 되므로 해당 tree의 모든 child 개수만큼, 즉 trie tree에 들어있는 모든 node 개수가 상한이다. 따라서 각 string의 length를 n, char 개수를 m이라고 하면 O(sum of nm)

 

공간복잡도

 insert, search시 string length만큼 stack이 쌓인다. 여기서 O(n). wildcard로 인해 재귀를 반복해도 DFS이기 때문에 string length만큼 stack이 쌓인다.

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

 

 

변경 : map 대신 array 사용

 위 코드는 map을 이용해 child를 할당해야 할 때마다 새로운 공간을 할당받는다. 또한 이런 pointer 방식은 random access이기 때문에 캐싱 이슈로 인해 속도가 느리다. 반면 딱 사용하는 pointer만 쓰기 때문에 memory 사용량이 적다. 실제 분석 결과를 보면 속도는 느리지만 메모리 사용량은 낮다.

 속도를 올리고 싶다면 vector나 array를 사용해 미리 공간을 할당해 둔다면 접근 시간이 줄게 된다. 시간복잡도나 공간복잡도는 변하지 않지만 접근하는 시간, 사용하는 공간이 상수배만큼 변한다. 실제로 코드를 돌려보면 runtime이 크게 향상된다.

// Runtime 1398 ms Beats 57.78%
// Memory 566.1 MB Beats 40.8%

struct TrieNode{
    bool isKey;
    TrieNode* next[26]; // *** 변경 : array로
    TrieNode():isKey(false){
        memset(next, NULL, sizeof(next));
    }
};

class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for(auto c: word){
            if(!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode(); // *** 변경 : map to array
            node = node->next[c - 'a'];
        }
        node->isKey = true;
    }
    
    bool search(string word) {
        return helper(word, root);
    }

private:
    TrieNode* root;
    
    bool helper(string word, TrieNode* node){
        for(int i = 0; i < word.size(); i++){
            char c = word[i];
            if(c != '.'){
                if(!node->next[c - 'a']) return false;
                node = node->next[c - 'a'];
            }
            else{
                bool found = false;
                int j = 0;
                for(; j < 26; j++){ // *** 변경 : map to array
                    if(node->next[j]) found |= helper(word.substr(i + 1), node->next[j]);
                    if(found) return true;
                }
                if(j == 26) return false;
            }
        }
        return node->isKey;
    }
};