백준 14425 문자열 집합(c++)

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

14425번: 문자열 집합

<코드>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	vector<string>v1;
	vector<string>v2;
	string a,b;
	while(n--)
	{
		cin>>a;
		v1.push_back(a);
	}
	sort(v1.begin(),v1.end());
	int cnt=0;
	while(m--)
	{
		cin>>b;
		if(binary_search(v1.begin(),v1.end(),b)){
			cnt++;
		}
	}
	cout<<cnt;
	
}

<풀이과정>

이분탐색으로 풀면 시간복잡도를 최소화할 수 있다. 일단 우선적으로 처음 문자열을 벡터에 넣은 후 정렬시켜주어야한다.(이분 탐색 전제조건) 그 후 오름차순 정렬된 문자열을 집합 S의 문자열들과 비교한다. binary_search 함수를 이용해 같다면 카운트해주면 된다.