[ SWEA 3135 ] 홍준이의 사전 놀이 (C++)

SWExpertAcademy의 홍준이의 사전놀이(3135 / D5) 문제이다.

[ 문제풀이 ]

본인은 이 문제를 자료구조 'TRIE'로 접근해 보았다.

[ 트라이(TRIE) 알아보기 ]

먼저, 트라이를 생성하기 위해서 선언한 TRIE 구조체 에서는 다음과 같은 3개의 멤버변수를 선언해서 관리해주 었다.

struct TRIE
{
    int Child;
    bool Finish;
    TRIE *Node[ALPHABET];
}
 

line 4)의 'Finish' 멤버변수는 현재 문자열의 마지막인지를 판단해주기 위해서 선언해놓은 멤버변수이다.

line 5)의 Node변수는 총 26칸(알파벳의 갯수)의 배열로 선언해 주었고, 이 노드를 통해서 단어들을 저장해 나갈 것이다.

사실 이 문제를 처음 구현할 때에는 line3) 의 'Child' 변수는 선언하지 않았었다.

단순히, 'Finish'변수와 'Node'변수를 통해서 트라이를 만들었고, 특정 문자열로 시작하는 문자를 찾을 때에도 모든 노드를

다 탐색하는 방식으로 구현하였더니, 정답은 나왔지만 제출시 시간초과를 받게 되었다.

그래서 line3)의 'Child'변수를 하나 만들어 주었다.

'Child' 멤버 변수는 "현재 자신의 노드를 통해서 만들 수 있는 단어의 갯수, 즉, 자신과 연결되어 있는 단어의 갯수" 를 관리해

주기 위한 용도이다.

따라서, 트라이의 문자열을 삽입하는 과정에서 Child변수의 값을 계속해서 ++ 시켜주는 과정이 필요하다.

메인문은 주어지는 코드이므로, 본인이 구현한 UserCode만 첨부하도록 하겠다.

[ 소스코드 ]

#define NULL 0
#define ALPHABET 26
#define NODE_MAX 1000000
 
struct TRIE
{
    int Child;
    bool Finish;
    TRIE *Node[ALPHABET];
 
    void Insert(char *Str);
    int Find(char *Str);
};
 
int N_Idx;
TRIE *Root, Nodepool[NODE_MAX];
 
TRIE *Nodeset()
{
    TRIE *NewNode = &Nodepool[N_Idx++];
    NewNode->Child = 0;
    NewNode->Finish = false;
    for (int i = 0; i < ALPHABET; i++) NewNode->Node[i] = NULL;
    
    return NewNode;    
}
 
void TRIE::Insert(char *Str)
{
    Child++;
    if (*Str == NULL)
    {
        Finish = true;
        return;
    }
 
    int Cur = *Str - 'a';
    if (Node[Cur] == NULL) Node[Cur] = Nodeset();
    Node[Cur]->Insert(Str + 1);
}
 
int TRIE::Find(char *Str)
{
    if (*Str == NULL) return Child;
    
    int Cur = *Str - 'a';
    if (Node[Cur] == NULL) return 0;
    return Node[Cur]->Find(Str + 1);
}
 
void init(void)
{
    N_Idx = 0;
    Root = Nodeset();
}
 
void insert(int buffer_size, char *buf)
{
    Root->Insert(buf);
}
 
int query(int buffer_size, char *buf)
{
    return Root->Find(buf);
}