[SWEA] 1256 - K번째 접미어

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

(이 글이 문제가 될 시 삭제하도록 하겠습니다.)

TRIE 유형을 다시 공부하게 되는 계기가 되었다.

접미어가 나올 수 있는 갯수가 문자열의 숫자랑 같기 때문에 그렇게 탐색에 많이 걸리지는 않는다.

입력받는 문자열을 모두 TRIE로 접미어화 시켜서 입력한다.

그 후에 문자열을 모두 끝까지 순회하면서 검색한다. 끝에 도달했을 때 숫자를 세면서 K번째가 되는 접미어를 찾는다.

순회하며 탐색할때는 vector로 구현해줘도 되고, 단순히 배열로 해줘도 되는데 간편하게 vector로 구현했다.

#include <iostream>
#include <malloc.h>
#include <cstring>
#include <vector>
using namespace std;
 
typedef struct NODE {
    int cnt[27];
    bool end;
    NODE* next[27];
}node;
 
int T, K, sum;
vector<char> dab;
 
node* makenode()
{
    node*tmp = (node*)malloc(sizeof(node));
    for (int i = 0; i < 27; i++)
    {
        tmp->next[i] = 0;
        tmp->cnt[i] = 0;
    }
    tmp->end = false;
    return tmp;
}
 
void insert(node *root, char* str, int st, int ed)
{
    node *tmp = root;
    if (st == ed) {
        tmp->end = true; return; }
    if (!tmp->next[str[st] - 'a']) tmp->next[str[st] - 'a'] = makenode();
    tmp->cnt[str[st] - 'a'] += 1;
    insert(tmp->next[str[st] - 'a'], str, st + 1, ed);
}
 
void find(node *root)
{
    node* tmp = root;
    if (tmp->end) sum++;
    if (sum == K) return;
    for (int i = 0; i < 27; i++)
        if (tmp->next[i])
        {
            dab.push_back(i + 'a');
            find(tmp->next[i]);
            if (sum == K) return;
            dab.pop_back();
        }
}
 
void deltrie(node *root)
{
    node *tmp = root;
    for (int i = 0; i < 27; i++)
        if (tmp->next[i]) deltrie(tmp->next[i]);
    free(tmp);
}
 
int main(void)
{
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        char arr[402];
        sum = 0;
        cin >> K;
        cin >> arr;
        int len = strlen(arr);
        while (!dab.empty()) dab.pop_back();
        node *root = makenode();
        for (int i = 0; i < len; i++)
        {
            if (!root->next[arr[i] - 'a']) root->next[arr[i] - 'a'] = makenode();
            root->cnt[arr[i] - 'a'] += 1;
            insert(root->next[arr[i] - 'a'], arr, i + 1, len);
        }
        find(root);
        deltrie(root);
        cout << "#" << tc << " ";
        for (int i = 0; i < dab.size(); i++)
            cout << dab[i];
        cout << endl;
    }
    return 0;
}