[C++] 백준 5052번: 전화번호 목록
문제 링크
문제 요약
주어진 전화 번호 중에 어떠한 전화번호가 다른 전화번호의 접두어가 되는 경우가 있는지 판별해야 한다.
접근 방법
트라이를 이용해서 풀었습니다. 먼저 입력으로 주어진 전화번호들을 모두 트라이에 집어 넣습니다. 그 다음에 각 전화번호로 순서대로 트라이에서 탐색을 합니다. 만약에 전화번호의 맨 마지막 번호에 해당하는 노드에 도달했을때, 자식 노드가 존재한다면 해당 전화번호는 다른 전화번호의 접두어가 될 수 있습니다.
트라이를 오늘 처음 공부했는데, KMP같은 다른 문자열 알고리즘보다는 이해하기 쉬워서 재밌게 푼 것 같습니다.
코드
#include <bits/stdc++.h>
using namespace std;
struct Trie {
Trie* child[10];
Trie() {
for (int i = 0; i < 10; i++)
child[i] = NULL;
}
void insert(string& numbers, int idx) {
if (idx == numbers.size())
return;
if (child[numbers[idx] - '0'] == NULL) {
Trie* trie = new Trie();
child[numbers[idx] - '0'] = trie;
}
child[numbers[idx] - '0']->insert(numbers, idx + 1);
}
bool check(string& numbers, int idx) {
if (idx == numbers.size()) {
for (int i = 0; i < 10; i++)
if (child[i] != NULL)
return false;
return true;
}
if (!child[numbers[idx] - '0']->check(numbers, idx + 1))
return false;
return true;
}
void clear(void) {
for (int i = 0; i < 10; i++) {
if (child[i] != NULL) {
child[i]->clear();
delete child[i];
}
}
}
};
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
Trie* root = new Trie();
vector<string> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
for (auto& i : v)
root->insert(i, 0);
bool flag = false;
for (auto& i : v) {
if (!root->check(i, 0)) {
flag = true;
break;
}
}
cout << (flag ? "NO\n" : "YES\n");
root->clear();
delete root;
}
return 0;
}
Author And Source
이 문제에 관하여([C++] 백준 5052번: 전화번호 목록), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beclever/C-백준-5052번-전화번호-목록저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)