반응형

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열이 trie에 있는지 체크하고, 있다면 NO를 출력하고, 그렇지 않다면 YES를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
 
using namespace std;
 
int n, t;
 
struct trie {
    trie* num[10];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) num[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete num[i];
        }
    }
 
    void insert(const char* ch) {
        if (!*ch) {
            this->end = true;
            return;
        }
 
        int now = *ch - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(ch + 1);
    }
 
    bool find(const char* ch) {
        if (!*ch || end) {
            return true;
        }
 
        int now = *ch - '0';
        if (!num[now]) return false;
        return num[now]->find(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        trie* root = new trie;
        bool flag = true;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char arr[11];
            cin >> arr;
 
            if (root->find(arr)) {
                if(flag) cout << "NO\n";
                flag = false;
            }
            else {
                root->insert(arr);
            }
        }
 
        if (flag) {
            cout << "YES\n";
        }
 
        delete root;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21

+ Recent posts

티스토리툴바