[문제풀이] 5052번: 전화번호 목록

[문제풀이] 5052번: 전화번호 목록

https://www.acmicpc.net/problem/5052

문제유형

TRIE

Solution

#include <stdio.h>
#include <malloc.h>
 
typedef struct tn
{
    int word;
    struct tn* child[10];
}NODE;
NODE root;
char str[10001][10 + 10];
char search_str[10 + 10];
 
int insert_node(char* str)
{
    int i, num;
    NODE* cur = &root;
    NODE* p;
    for (i = 0; str[i]; i++)
    {
        num = str[i] - '0';
        if (cur->child[num] == 0)
        {
            p = (NODE*)calloc(1, sizeof(NODE)); 
            if (!p) return 0;    //코드검사용 동적할당받을 때 체크해라
            cur->child[num] = p;
        }
        cur = cur->child[num];
    }
    cur->word = 1;
    return 1;
}
 
int search_string(char* str)
{
    NODE* cur = &root;
    int i, num;
 
    for (i = 0; str[i]; i++)        
    {
        if (cur->word == 1) return 0;
        num = str[i] - '0';
        if (cur->child[num] == 0) return 0;
        cur = cur->child[num];
    }
    return cur->word;
}
 
void print_node(NODE* node, int n)
{
    int i;
    if (node != 0 && node->word == 1)
    {
        printf("%s\n", search_str);        //문자열의 마지막에 도달하면 출력.    
    }
    if (node == 0) return;    
    for (i = 0; i < 10; i++)
    {
        if (node->child[i])
        {
            search_str[n] = i + '0';
            search_str[n + 1] = 0;    //출력문자를 SEARCH_STR에 저장하고 매번 N+1에 0으로 끝문자를 넣어주자.
            print_node(node->child[i], n + 1);
        }
    }
}
 
void delete_node(NODE* node)
{
    int i;
    for (i = 0; i < 10; i++)
    {
        if (node->child[i])
        {
            delete_node(node->child[i]);
            free(node->child[i]);
            node->child[i] = 0;
        }
    }
}
 
int main()
{
    int t, n, i, flag = 0;
    scanf("%d", &t);
    while (t--)
    {        
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%s", str[i]);
            insert_node(str[i]);
        }
 
        flag = 0;
        for (i = 0; i < n; i++)
        {
            int sol = search_string(str[i]);
            if (sol == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag) printf("NO\n");
        else printf("YES\n");
 
        delete_node(&root);
    }
    return 0;
}