전화번호 목록
문제
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
오랜만에 백준 포스팅이다.
문제를 간단히 요약하자면 전화번호 목록들 중 중복되는 경우가 있는지 찾는 문제였다. 중복의 결과에 따라 YES혹은 NO를 출력해주면 된다.
사고과정
처음에는 그냥 트라이 구조를 만든 뒤 DFS를 통해 검사하자는 생각이 들었다. 그래서 구현하고 풀었더니 시간초과가 났다.
그래서 최적화 할 수 있는 방법들이 뭐가 있을까 많은 고민을 했다.
- 트라이 구조를 만드는 과정에서 이전에 트라이 구조로 만들었던 문자열의 끝을 만나면 NO, 트라이가 잘 만들어 지면 YES를 출력하도록 하니 길이가 긴 문자열이 들어오고 그 뒤의 짧은 문자열이 들어올 시 검사할 방도가 없어 틀렸다.
- 검사하는 과정에서 모든 노드 순회를 하지않고 NO라는 사실이 밝혀지면 바로 리턴하도록 했더니 시간초과가 났다.
그래서 엄청 답답했었는데 첫번째 방법에서 문자열을 모두 입력받은 뒤 문자열의 길이에 따라 오름차순으로 정렬하면 된다는 것을 깨닳았다.
사실 알고리즘 분류 확인했다.
풀이
struct node{
int num; // 필요?
bool flag = false;
node* iterArr[10] = {nullptr};
};트라이를 만들 간단한 노드 구조이다. 숫자는 0부터 9까지 있다는 것을 착안해 크기가 10인 배열로 자식 노드들을 표현할 수 있도록 했다. 저 num의 경우 배열의 인덱스로 대체가 가능해 사실 사용되지 않는다.
void INIT(){
node* root = new node;
vector<pair<int, string>> vec;
int n;
cin >> n;
for(int i=0; i<n; i++){
string temp;
cin >> temp;
vec.push_back({temp.size(), temp});
}
sort(vec.begin(), vec.end());
/*print*/
// for(int i=0; i<vec.size(); i++){
// cout << vec[i].second << "\n";
// }
// cout << "\n";
for(int i=0; i<n; i++){
string temp = vec[i].second;
node* nodeIter = root;
for(int i=0; i<temp.size(); i++){
if(nodeIter->iterArr[temp[i]-48] == nullptr){
// insert
nodeIter->iterArr[temp[i]-48] = new node;
nodeIter = nodeIter->iterArr[temp[i]-48];
if(i == temp.size()-1){
nodeIter->flag = true;
}
}else{
nodeIter = nodeIter->iterArr[temp[i]-48];
if(nodeIter->flag){
cout << "NO\n"; // 빠른 중닫
return;
}
}
}
}
cout << "YES\n";
}이후 트라이 구조를 만들어가며 기존에 이미 넣어두었던 문자열을 만나면 NO라는 메세지와 함께 반환되도록 하고 트라이구조가 정상적으로 만들어지면 YES라는 메세지가 나오도록 했다.
전체코드
// BOJ 5052
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct node{
int num; // 필요?
bool flag = false;
node* iterArr[10] = {nullptr};
};
void INIT(){
node* root = new node;
vector<pair<int, string>> vec;
int n;
cin >> n;
for(int i=0; i<n; i++){
string temp;
cin >> temp;
vec.push_back({temp.size(), temp});
}
sort(vec.begin(), vec.end());
/*print*/
// for(int i=0; i<vec.size(); i++){
// cout << vec[i].second << "\n";
// }
// cout << "\n";
for(int i=0; i<n; i++){
string temp = vec[i].second;
node* nodeIter = root;
for(int i=0; i<temp.size(); i++){
if(nodeIter->iterArr[temp[i]-48] == nullptr){
// insert
nodeIter->iterArr[temp[i]-48] = new node;
nodeIter = nodeIter->iterArr[temp[i]-48];
if(i == temp.size()-1){
nodeIter->flag = true;
}
}else{
nodeIter = nodeIter->iterArr[temp[i]-48];
if(nodeIter->flag){
cout << "NO\n"; // 빠른 중닫
return;
}
}
}
}
cout << "YES\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--){
INIT();
}
return 0;
}Summary
- 짧은 문자열 부터 트라이 구조로 만들어 나가는 것으로 불필요한 탐색 및 검사 최소화.
PS
골드 하위문제라 별 고민 없이 풀었는데 꽤나 고전했다. 이렇게 정리하다 보니 꽤다 간단한 문제였다. PS에 있어서 난이도는 개개인마다 느끼는 정도가 많이 다른가보다. 꾸준히 푸는것만이 답인 것 같다.
티어에도 집착하지 않도록 해야겠다. 요즘들어 티어 상승의 욕심이 많아져 별 고민없이 해설을 찾아보는 경우가 늘어나는 것 같다. 그러면 PS하는게 무슨 의미가 있나 생각이 든다. 고생좀 하더라도 더 고민해보고 꼼꼼히 따져보는 습관을 들여야겠다. 어떤 문제든 사고과정이나 해결방법이 어렵게 느껴지는 게 있다고 생각한다. 진짜 PS괴물들은 오래 고민하는거에 두려워 하지 않고 하나하나 꼼꼼히 따져가며 최적의 알고리즘을 찾아내고 이용하는 것이 아닐까 생각이든다.
그리고 벨로그도 자주 작성해야겠다.
