[알고리즘 풀이 분석] BOJ 5052 전화번호 목록
오늘 풀어본 문제는 BOJ 5052 전화번호 목록 이다.
예상치 못하게 다음주에 면접이 생겨 준비중인데 자료구조부터 정리하다가 Trie
관련된 추천 문제가 있어 풀어보았다. 사실 트라이를 처음 써보는 것 같은데 개념적으로는 이해가 금방 됐지만 손으로 구현하려면 좀 더 연습이 필요할 것 같다..!
BOJ 5052 전화번호 목록
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입출력
[입력]
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
[출력]
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
나의 풀이
이문제를 푸는데 있어 나의 목표는 자료구조 Trie
를 구현해보고 활용 해 보는 것이었다. 이론 공부를 하면서 이애하고 트라이를 구현 해 두었지만 문제 조건에 맞게 바꾸는 과정에서 역시 좀 헷갈렸다.
주어지는 번호들이 모두 서로의 접두어가 되지 않으면 "YES" 를 출력, 하나라도 접두어가 되는 경우가 존재한다면 "NO" 를 출력하는 문제였다.
Trie
에 문자열을 넣으면서 확인해 보려 했는데 너무 헷갈려서 일단 넣고 나중에 확인하는 방식으로 진행하였다.
입력되는 문자열들을 char 배열 char numbers[10001][11]
에 차례대로 넣으면서 Trie
에 삽입해두고 이후에 각 문자열들을 Trie
내에서 검사하면서 해당 문자열이 끝나기 전에 Trie
에 연결된 노드가 끝나면, 즉 해당 문자열의 접두어인 문자열이 존재하면 false
값을 반환하였다.
아직 몇번 더 연습이 필요할 것 같다!
코드
#include <iostream>
#include <vector>
// boj 5052 전화번호 목록, Trie 사용, 골드 4
using namespace std;
struct TRIE {
bool finish;
TRIE * Node[26];
TRIE() {
finish = false;
for (int i = 0; i < 26 ; ++i) Node[i] = NULL;
}
void insert(char * str){
if (*str == NULL){
finish = true;
return;
}
int cur = *str - '0';
if (Node[cur] == NULL){
Node[cur] = new TRIE();
}
Node[cur]->insert(str+1);
}
bool check(char * str) {
if(*str == NULL) return true;
if (finish) return false;
int cur = *str - '0';
return Node[cur]->check(str+1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin>>T;
for (int i = 0; i < T; ++i) {
int N;
cin>>N;
char numbers[10001][11];
TRIE * root = new TRIE();
for (int j = 0; j < N; ++j) {
cin>>numbers[j];
root->insert(numbers[j]);
}
bool consistent = true;
for (int j = 0; j < N; ++j) {
if (!(root->check(numbers[j]))) {
consistent = false;
break;
}
}
if (!consistent) cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
}
return 0;
}
Reference
Author And Source
이 문제에 관하여([알고리즘 풀이 분석] BOJ 5052 전화번호 목록), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nnnyeong/알고리즘-풀이-분석-BOJ-5052-전화번호-목록저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)