백준 5052 전화번호 목록(c++)

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

5052번: 전화번호 목록

<코드>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
bool consistency(vector<string>v){
	for(int i=0;i<v.size()-1;i++){
		string cur = v[i];
		string next = v[i+1];
		int cnt=0;
		for(int j=0;j<cur.size();j++){
			if(next[j]==cur[j]) cnt++;
		}
		if(cnt == cur.size()) return false; 
	}
	return true;
}
int main()
{
	vector<string>v;
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
			string num;
			cin>>num;
			v.push_back(num);
		}
		sort(v.begin(),v.end());
		bool ans = consistency(v);
		if(ans == true) cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
		v.clear();	
	}	
}

<풀이 과정>

이 문제는 한 문자열이 다른 문자열의 접두어인지 아닌지는 판별하는 문제이다.

접두어는 파생어를 만드는 접사로서 어근이나 단어의 앞에 단어가 붙어 새로운 단어를 만드는 경우이다.

예시 입출력

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

첫번째 3개의 문자열이 왔는 경우에는 

25426 앞에 911라는 단어가 붙어 새로운 단어를 만들었기 때문에, 일관성이 없는 경우이다. 

하지만 두번째 예시는 다른 문자열이 어떤 다른 문자열에도 접두어가 될 수 없다.

그래서, 우선적으로 string 벡터를 만들어 준 후, 문자열의 길이를 기준으로 오름차순 정렬시켜준다.

그 이후에 각 기존 문자열의 문자랑 다음 문자열의 문자를 하나하나씩 비교해준다.

(다음 문자열의 길이>기존 문자열의 길이)

만약에 비교부분에서 다음 문자열의 길이의 일부가 기존 문자열과 같다면 false를 반환하고 그렇지 않으면 true를 반환해주면 끝이다.

<코드 참조>

https://g-idler.tistory.com/91  

[백준][C++] 5052. 전화번호 목록