백준 전화번호 목록 [c++]
5052 전화번호 목록 골드 5
문제
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
풀이
전화번호 부에서 접두사가 일치하는지 여부를 조사하는 문제이다.
처음에는 map을 사용해 전화번호부를 저장하고 (저장되면 크기 순으로 정렬됨) 크기가 자신보다 큰 번호의 접두사 여부를 확인하는 2중 for문으로 코드를 짰다.(아래 코드 1)
그런데 시간초과가 되어, map에 대해 찾아보니 unordered map을 알게 됬다.
unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이고
map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
따라서 굳이 정렬될 필요가 없다면 데이터 양이 많을 경우 unordered map이 훨씬 유리하다.
또한 substring을 찾는 코드를 구현하지 않아도, string.h에 substr함수가 존재한다는 것을 알게 됬다.
map을 사용하는 코드를 unordered map으로 수정하니, 시간초과가 해결되었다. (코드 2)
코드 1(map을 사용한 2중 for문)
#include <iostream>
#include <map>
#include <string.h>
#include <iterator>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, n;
map<string, int> book;
cin >> t;
for(int i = 0; i < t; i++)
{
cin >> n;
int verified = 1;
for(int i = 0; i < n; i++)
{
string phone;
cin >> phone;
book[phone] = phone.size();
}
for(auto iter = book.begin(); iter != prev(book.end()); ++iter)
{
string head = iter->first;
int size = iter->second;
for(auto next_iter = next(iter); next_iter != book.end(); ++next_iter)
{
string cmp = next_iter->first;
int cmp_size = next_iter->second;
if(cmp_size > size){
if(head.compare(0,size,cmp,0,size) == 0){
verified = 0;
break;
}
}
}
if(verified == 0){
break;
}
}
if(verified == 0){
cout << "NO" << endl;
} else{
cout << "YES" << endl;
}
book.clear();
}
return 0;
}코드 2 (unordered map + substr)
#include <iostream>
#include <unordered_map>
#include <string.h>
#include <iterator>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, n;
unordered_map<string, int> book;
vector<string> phone;
cin >> t;
for(int i = 0; i < t; i++)
{
cin >> n;
int verified = 1;
for(int i = 0; i < n; i++)
{
string number;
cin >> number;
phone.push_back(number);
book[number] = 1;
}
for(int i = 0; i < phone.size(); i++)
{
for(int j = 0; j < phone[i].size() - 1; j++)
{
string subs = phone[i].substr(0, j + 1);
if(book[subs]){
verified = 0;
}
}
}
if(verified == 0){
cout << "NO" << endl;
} else{
cout << "YES" << endl;
}
book.clear();
phone.clear();
}
return 0;
}