https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
트라이를 연습하려고 풀었던 문제입니다.
트라이에 주어지는 전화번호들을 전부 넣은 다음, 넣었던 전화번호들을 트라이 안에서 검색합니다.
검색하던 도중 해당 전화번호까지 가기 전에 isEnd를 만나면 접두어가 있다는 뜻이므로 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
77
78
79
80
81
82
83
84
85
86
87
|
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#define MAX 10001
using namespace std;
char list[MAX][11];
int N;
int charToInt(char x) {
return x - '0';
}
typedef struct Trie {
bool isEnd;
Trie *next[10];
Trie() : isEnd(false) {
memset(next, 0, sizeof(next));
}
~Trie() {
for (int i = 0; i < 10; i++) {
if (next[i]) delete next[i];
}
}
void insert(char *key) {
if (*key == '\0') {
isEnd = true;
}
else {
int idx = charToInt(*key);
if (!next[idx]) next[idx] = new Trie();
next[idx]->insert(key + 1);
}
}
bool find(char *key) {
if (*key == '\0') return true;
if (isEnd) return false;
int idx = charToInt(*key);
return next[idx]->find(key + 1);
}
}Trie;
Trie *t;
void func() {
for (int i = 0; i < N; i++) {
if (!(t->find(list[i]))) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
void input() {
t = new Trie();
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
t->insert(list[i]);
}
}
void init() {
delete t;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
init();
}
return 0;
}
|
cs |
'algorithm > Trie' 카테고리의 다른 글
| boj 14725 개미굴 (0) | 2022.03.27 |
|---|