[SWEA] 3135. 홍준이의 사전놀이

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS

 

시간 복잡도를 어림잡아 계산해보니 특별한 알고리즘을 사용하지 않아도 시간 안에 실행될것 같았지만,

 

문제의 힌트에 Trie라는 개념을 사용하면 된다는 말에, 

 

구글링을 해서 Trie를 익히고 적용하여 풀게 되었습니다.

 

https://twpower.github.io/187-trie-concept-and-basic-problem

[Algorithm] 트라이(Trie) 개념과 기본 문제

이 분 글을 참고해서 Trie 개념을 익혔고 

 

문제에 적용했으나, 시간 초과 error를 받았습니다.

 

정적할당을 시도 해봤지만, 구현 방법을 모르겠어서 

 

트리를 구현하는 코드는 그대로 두고, query가 들어왔을 때, 문자의 개수를 세는 부분만 바꾸게 되었습니다. 

 

https://colorscripter.com/s/ZMKSUkT

시간 초과했던 코드입니다. 

 

#define ALPHABET_NUM 26
int char2int(char chr);
struct Trie
{
    bool is_Terminal;
    Trie* child[ALPHABET_NUM];
    Trie() :is_Terminal(false)
    {
        for (int i = 0; i < ALPHABET_NUM; i++)
            child[i] = 0;
    }
    void insert_Trie(int buff_size, char* buf)
    {
        if (buff_size == 0)
        {
            is_Terminal = true;
            return;
        }
        int chrInt = char2int(*buf);
        if (child[chrInt] == 0)
            child[chrInt] = new Trie();
        child[chrInt]->insert_Trie(buff_size - 1, buf + 1);
    }
    Trie* find(int buff_size, char* buf)
    {
        if (buff_size == 0)
            return this;
        else
        {
            int chrInt = char2int(*buf);
            if (child[chrInt] == 0)
                return nullptr;
            return child[chrInt]->find(buff_size - 1, buf + 1);
        }
    }
    int TreeNum()
    {
        int sum = is_Terminal;
        for (int i = 0; i < ALPHABET_NUM; i++)
            if (child[i] != 0)
                sum += child[i]->TreeNum();
        return sum;
    }
};
Trie* rootNode;
void init(void) {
    rootNode = new Trie();
}
 
void insert(int buffer_size, char* buf) {
    rootNode->insert_Trie(buffer_size, buf);
}
 
int query(int buffer_size, char* buf) {
    Trie* foundOne = rootNode->find(buffer_size, buf);
    if (foundOne == nullptr)
        return 0;
    return foundOne->TreeNum();
}
int char2int(char chr)
{
    return chr - 'a';
}
 
 

 

 

object constructor에서 child의 각 포인트에 0을 Assign 합니다.

이 사실을 통해서 query로 들어온 prefix로 시작하는 단어가 있는지 없는지를 구별합니다. 

(insert할때, child[chrIdx]==0일때, 새로운 Trie object의 주소값을 할당하므로, 

query로 들어온 prefix로 시작하는 단어가 이미 있다면, child[chrIdx]의 값이 0이 아닐 것입니다.)

 

query로 들어온 prefix로 시작하는 단어가 존재할때, 그 단어들의 개수를 세기 위한 method입니다. 

subtree를 순회하면서 각 node의 is_Terminal를 더합니다.

 

이 문제의 time complexity는, 대략적으로 O(nlogn)이라고 할 수 있을 것입니다.(log의 밑이 애매하지만)

insert보다, query의 cost가 더 크겠지만, (subtree를 전부 순회해야 하므로) 대략적으로는 그렇습니다.

 

n<=10^5이므로, 제한시간 4초 안에 작동할것 같았지만, 시간 초과 error가 뜨네요...

 

댓글을 보니, 문제 조건과 다르게 n이 10^5 이상인 것 같습니다.

 

어쨌든, 풀어야 하니까. query에서 subtree를 전부 순회하는 부분을 수정했습니다. 

 

http://colorscripter.com/s/gqFx28V

수정된 코드입니다. 

 

#define ALPHABET_NUM 26
int char2int(char chr);
struct Trie
{
    bool is_Terminal;
    int childNum;
    Trie* child[ALPHABET_NUM];
    Trie() :is_Terminal(false), childNum(0)
    {
        for (int i = 0; i < ALPHABET_NUM; i++)
            child[i] = 0;
    }
    void insert_Trie(int buff_size, char* buf)
    {
        childNum++;
        if (buff_size == 0)
        {
            is_Terminal = true;
            return;
        }
        int chrInt = char2int(*buf);
        if (child[chrInt] == 0)
            child[chrInt] = new Trie();
        child[chrInt]->insert_Trie(buff_size - 1, buf + 1);
    }
    Trie* find(int buff_size, char* buf)
    {
        if (buff_size == 0)
            return this;
        else
        {
            int chrInt = char2int(*buf);
            if (child[chrInt] == 0)
                return nullptr;
            return child[chrInt]->find(buff_size - 1, buf + 1);
        }
    }
    int TreeNum()
    {
        return childNum;
    }
};
Trie* rootNode;
void init(void) {
    rootNode = new Trie();
}
 
void insert(int buffer_size, char* buf) {
    rootNode->insert_Trie(buffer_size, buf);
}
 
int query(int buffer_size, char* buf) {
    Trie* foundOne = rootNode->find(buffer_size, buf);
    if (foundOne == nullptr)
        return 0;
    return foundOne->childNum;
}
int char2int(char chr)
{
    return chr - 'a';
}
 

 

 

Trie struct에 'childNum' attribute를 추가해서 

insert를 해가면서 path에 있는 node들의 childNum에 +1씩 해줍니다. 

 

query를 수행할때, subtree를 순회하지 않고,

subtree의 rootNode의 childNum만 참조하면, 

subtree에 있는 단어들의 개수를 알 수 있습니다. 

 

 

어느 피드백이든 환영합니다!