[ BOJ 백준 5052번 - 전화번호 목록 ] 해설 및 코드

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

목적

전화 번호 목록이 주어졌을 때, 일관성 있는 목록인지 아닌지 구한다. (문제에서 말하는 일관성 없는 목록이라 함은, 어떤 번호가 다른 번호의 앞부분에 매칭된다는 뜻이다.)

 

접근법

1. 트라이 자료구조를 연습할 수 있는 기본 문제로서, 트라이 구조체만 구현하면 쉽게 풀 수 있다. 이외에도 정렬하여 인접한 문자열만 비교하거나, 해싱을 통해서 해결 가능하다. 트라이를 사용하는 접근과 정렬을 사용하는 접근, 두 가지로 풀어보았다.

 

• 트라이 자료구조 사용

#include<iostream>
#define endl '\n'
using namespace std;
 
struct trie{
    trie* children[10];
    bool isEndOfPhone;
};
 
bool insert(trie* root,string& phone){
    trie* parent=root;
    
    for(int i=0;i<phone.length();++i){
        trie** child=&parent->children[phone[i]-'0'];
        if(parent->isEndOfPhone) return false;
        if(!*child) *child=new trie{{0},false};
        parent=*child;
    }
    for(int i=0;i<10;++i)if(parent->children[i])return false;
    return parent->isEndOfPhone=true;
}
 
bool solve(){
    trie* root=new trie{{0},false};
    int n;cin>>n;
    string phone;
    for(int i=0;i<n;++i){
        cin>>phone;
        if(!insert(root, phone)){
            while(++i<n)cin>>phone;
            return false;
        }
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;cin>>t;
    while(t--)cout<<(solve()?"YES":"NO")<<endl;
}
 

 

• 정렬 하여 인접한 요소만 비교

#include<iostream>
#include<algorithm>
#define endl '\n'
using namespace std;
 
bool check(string& a,string& b){
    int len=min(a.length(),b.length());
    for(int i=0;i<len;++i)if(a[i]!=b[i])return false;
    return true;
}
 
bool solve(){
    int n;cin>>n;
    string list[10000];
    for(int i=0;i<n;++i)cin>>list[i];
    sort(list,list+n);
    for(int i=1;i<n;++i)if(check(list[i-1],list[i]))return false;
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;cin>>t;
    while (t--)cout<<(solve()?"YES":"NO")<<endl;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.