문제 이해
- 전화번호 목록이 주어진다.
- 전화목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
- 전화번호 목록이 일관성이 있는지 없는지 구하라.
<조건>
- 시간 제한: 1초
- 메모리 제한: 256MB
<입력>
t: 테스트 케이스 개수 (1 ~ 50, 10^1)
n: 전화번호 수 (1 ~ 10,000, 10^4)
<출력>
각 테스트 케이스에 대하여, 일관성이 있다면 YES, 없다면 NO를 출력하라.
문제 풀이
전화 번호 수의 최댓값이 10,000이고, 테스트 케이스가 최대 50개까지 가능하므로
한 케이스가 O(n^2)의 복잡도를 가질경우 시간초과가 날 수밖에 없다.
그러므로, 브루트포스로는 풀 수 없었다.
이 문제를 푸는 핵심은 바로 string 배열의 정렬에 있었다.
stl 라이브러리에 있는 sort()함수를 string 배열에 사용할 시
같은 자리에 있는 알파벳의 대소 비교가 길이 비교보다 더 우선시된다!
예를 들어
ab
az
abc 라는 배열이 있을 때
sort()를 통해 정렬할 경우
ab
abc
az 순으로 나열되는 것이다.
이 점만 알고 있다면 문제를 매우 쉽게 풀 수 있을 것이다!!!
정렬한 후에는
접두어가 있는지 없는지에 대해서 두 개의 연속된 문자열만 비교해주면 된다.
bool flag = true;
for(int i = 0; i < n-1; i++){
string a = v[i];
string b = v[i+1];
if(a.size() >= b.size()) continue;
if(a == b.substr(0, a.size())){
flag = false;
break;
}
}
전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--){
vector <string> v;
int n;
cin>>n;
for(int i = 0; i < n; i++){
string s;
cin>>s;
v.push_back(s);
}
sort(v.begin(), v.end());
bool flag = true;
for(int i = 0; i < n-1; i++){
string a = v[i];
string b = v[i+1];
if(a.size() >= b.size()) continue;
if(a == b.substr(0, a.size())){
flag = false;
break;
}
}
if(flag) cout<<"YES\n";
else cout<<"NO"<<"\n";
}
return 0;
}
배운 점
string을 sort 함수를 통해 정렬할 경우 같은 자리에 있는 알파벳 대소비교가 우선이라는 걸 배울 수 있었다!
문자열도 정말 무궁무진한거 같다.