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

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

(이 포스팅이 문제가 될 경우 삭제하도록 하겠습니다)

삼성 SW Test B형을 준비하면서 건드렸다가 TRIE라는 새로운 알고리즘을 공부하게 해준 문제

그냥 말그대로 TRIE를 구현하고, 조건의 문자열로 시작하는 문자열이 몇개가 되는지 반환하는 문제

다만, 문자열의 갯수를 저장하는 cnt배열을 각 노드안에 만들어서 각 문자열이 각 노드에서 몇번이나 중복되는지 검사

ex) ippp, ippx, ip와 같이 입력되고, ipp로 시작되는 것을 찾으라 할때,

첫번째 노드에서 i 는 3개, 두번째 노드에서 p는 3개, 세번째 노드에서 p 는 2개, 그다음 노드는 p 1개, x 1개

그러나 ipp로 시작되는 것은 세번째 노드의 cnt['p' - 'a']의 2개가 답이 된다

query 외에는 각 함수를 완성시키는 것은 개인이 TRIE를 공부해 보았다면 쉽게 할 수 있다

다만... 입출력이 너무커서 시간은 3847ms로 간신히 통과...

Main부분은 주어지기 때문에 User code부분만 올렸습니다.

#include <cstdlib>
 
typedef struct NODE {
    int cnt[30];
    int end;
    NODE *next[30];
}node;
 
void delnode(node *del)
{
    node *tmp = del;
    for (int i = 0; i < 30; i++)
        if (tmp->next[i]) delnode(tmp->next[i]);
    free(tmp);
    return;
}
 
node *makenewnode()
{
    node *tmp = (node*)malloc(sizeof(node));
    for (int i = 0; i < 26; i++) { tmp->next[i] = 0; tmp->cnt[i] = 0; }
    tmp->end = 0;
    return tmp;
}
 
node *root = makenewnode();
 
void init(void) {
    node *tmp = root;
    delnode(tmp);
    node *root = makenewnode();
    return;
}
 
void insert(int buffer_size, char *buf) {
    node *tmp = root;
    for (int i = 0; i < buffer_size; i++)
    {
        if (!tmp->next[buf[i] - 'a']) tmp->next[buf[i] - 'a'] = makenewnode();
        tmp->cnt[buf[i]-'a']++;
        tmp = tmp->next[buf[i] - 'a'];
    }
    tmp->end = 1;
}
 
int query(int buffer_size, char *buf) {
    node*tmp = root;
    for (int i = 0; i < buffer_size - 1; i++)
        if (!tmp->next[buf[i] - 'a']) return 0;
        else tmp = tmp->next[buf[i] - 'a'];
    return tmp->cnt[buf[buffer_size - 1] - 'a'];
}