[백준] 1764 - 듣보잡

알고리즘 단톡방에 어떤분의 요청으로 stl map이나 hash를 사용하지 않고 푼 코드가 있냐고 물어보길래 trie를 사용해서 풀어보았다

1. N개의 문자열이 들어오는 순서대로 TRIE안에 넣어준다.

 - 이때 마지막 문자열의 길이가 끝날 때는 NODE의 end를 true로 바꾸어 노드가 끝났음(문자열의 마지막)을 표시한다.

2. 이 후 M개의 문자열이 들어오는 순서대로 N개의 문자열이 들어 있는 TRIE에 넣어 비교한다.

 

3. 문자열이 탐색하다가 next 문자가 NULL포인터를 가지거나, 문자열이 끝났음에도 end가 false인 경우는 그냥 리턴

4. 찾을 경우에는 dab_cnt를 하나 늘려서 리턴한다

5. check함수를 모두 빠져 나왔을 때 답을 찾은 것인지 체크하기 위한 check_num과 비교하여 달라 졌을 경우에는 dab배열에 str을 복사해서 넣는다.

 - 그리고는 check_num을 갱신한다.

6. 답의 갯수를 출력하고 사전순으로 답을 정렬한 다음 출력(이 부분은 귀찮아서 stl을 사용함...)

7. 메모리 해제 후 종료

#include <iostream>
#include <malloc.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef struct NODE {
    bool end;
    NODE *next[30];
}node;
 
NODE *makenode() {
    NODE*tmp = (NODE*)malloc(sizeof(NODE));
    tmp->end = false;
    for (int i = 0; i < 26; i++)
        tmp->next[i] = NULL;
    return tmp;
}
 
int dab_cnt;
char dab[500001][21];
 
void insert(int d, NODE *root, char *buff) {
    NODE *tmp = root;
    if (strlen(buff) == d) {
        tmp->end = true;
        return;
    }
    if (tmp->next[buff[d] - 'a'] == NULL) {
        tmp->next[buff[d] - 'a'] = makenode();
    }
    insert(d + 1, tmp->next[buff[d] - 'a'], buff);
}
 
void check(int d, NODE *root, char*buff) {
    NODE*tmp = root;
    if (strlen(buff) == d) {
        if (tmp->end) dab_cnt++;
        return;
    }
    if (tmp->next[buff[d] - 'a'] == NULL) return;
    else {
        check(d + 1, tmp->next[buff[d] - 'a'], buff);
    }
}
 
void del(NODE* root) {
    NODE *tmp = root;
    for (int i = 0; i < 26; i++) {
        if (tmp->next[i] != NULL)
            del(tmp->next[i]);
    }
    free(tmp);
}
 
int main(void) {
    int N, M;
    NODE *root = makenode();
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        char str[21];
        cin >> str;
        insert(0, root, str);
    }
    int check_num = dab_cnt;
    for (int i = 0; i < M; i++) {
        char str[21];
        cin >> str;
        check(0, root, str);
        if (check_num != dab_cnt) {
            for (int j = 0; j < strlen(str); j++)
                dab[check_num][j] = str[j];
            check_num = dab_cnt;
        }
    }
 
    cout << dab_cnt << endl;
    vector<string> arr;
    for (int i = 0; i < dab_cnt; i++)
        arr.push_back(dab[i]);
    sort(arr.begin(), arr.end());
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i].c_str() << endl;
    }
    del(root);
    return 0;
}