[SWEA] 1257 - K번째 문자열

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

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

이 문제도 K번째 접미어 처럼 TRIE로 풀면 된다.

TRIE를 사용하는 이유는 입력과 동시에 자동으로 정렬하는 효과를 볼 수 있기 때문이다.

순회하며 순서대로 탐색하기 때문이다.

일단 입력되는 문자열을 TRIE로 만들어 준다.

순회하며 처음 방문하는 node에 check를 하며 갯수를 세준다.

이때 중복되는, 문제에서 처럼 food 의 경우는 o가 두번 나오게 되는데 node에 check 변수를 넣어주는 이유는 이 중복을 제거하기 위해서이다.

따라서 현재 방문한 노드에 check가 false라면 갯수를 카운트 하지만, 아니라면 다음 노드를 검색해서 들어가는 것으로 중복을 제거할 수 있다.

이것도 순회하며 탐색할 때 vector로 push와 pop을 해주며 dab을 뽑아냈다.

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