백준 5052 전화번호 목록 C++

간단한 해설

 

앞에서부터 접두어를 확인해서 존재유무를 파악하면 된다.

 

입력이 다음과 같다고 생각해보자.

 

2

2
909
9099

2

9099
909

 

두 입력값의 답은 모두 NO이다.

 

먼저 처음 값이 909이므로, 9, 90, 909 모두 존재하는지 확인한다.

 

두번째 입력 또한, 존재하는지 확인해야하는데, 이를 위해서 vector<string> 배열로 입력값을 모두 입력받은 뒤, sort함수를 활용하여서 정답값을 올바르게 출력하도록 유도한다.

 

이전에 입력한 배열값이 존재하는지 확인할려면, 여러 방법이 있겠지만 나는 map을 활용하였다.

c++에서는 BST로 map을 구현하기 때문에 find()나 count()로 O( log(n) )에 값 조회를 할 수 있다.

 

답

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t-->0){
		int n;
		cin>>n;
		map<string,int> m;
		bool state=false;
		vector<string> str(n);
		for(int i=0;i<n;++i){
			cin>>str[i];
		}
		sort(str.begin(),str.end());
		for(int i=0;i<n;++i){
			string tmp="";
			for(int j=0;j<str[i].size();++j){
				tmp+=str[i][j];
				if(m.count(tmp)>0){
					state=true;
					break;
				}
			}
			m.insert({str[i],1});
			if(state) break;
		}
		if(state) cout<<"NO\n";
		else cout<<"YES\n";
	}
}