14425 번 : 문자열 집합

문제는 다음과 같습니다.

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

14425번: 문자열 집합

 

풀이 코드는 다음과 같습니다.

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

using namespace std;

int main() {
	int n,m;
	cin>>n>>m;
	vector<string>v(n);
	for(int i{0};i<n;i++)
	{
		cin>>v[i];
	}
	int count{0};
	sort(v.begin(),v.end());
	for(int i{0};i<m;i++)
	{
		string tmp;
		cin>>tmp;
		if(binary_search(v.begin(),v.end(),tmp))
			count++;
	}
   cout<<count;
   return 0;
}

아마 많은 사람들이 vector를 사용하면 find로 값을 찾을 것이라고 생각합니다.

그래서 다음과 같은 코드를 사용해서 제출하는 사람도 있었을 것이라 생각합니다.

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

using namespace std;

int main() {
	int n,m;
	cin>>n>>m;
	vector<string>v(n);
	for(int i{0};i<n;i++)
	{
		cin>>v[i];
	}
	int count{0};
	for(int i{0};i<m;i++)
	{
		string tmp;
		cin>>tmp;
		if(find(v.begin(),v.end(),tmp)!=v.end())
			count++;
	}
   cout<<count;
   return 0;
}

하지만 문자열의 개수가 10,000개 주어지기 때문에 일일이 모든 원소를 찾아보게 되면 시간초과에 걸릴 수 있습니다.

따라서 이진 탐색을 사용하였고 이진 탐색의 경우에는 vector를 정렬해서 사용해야 합니다.

그 점만 잊지 않고 푸신다면 해결할 수 있는 문제였습니다.