백준 1764 듣보잡(c++)

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

1764번: 듣보잡

<코드>

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

int main()
{
	int n,m;
	cin>>n>>m;
	vector<string>s1;
	vector<string>s2;
	vector<string>result;
	for(int i=0;i<n;i++)
	{
		string a;
		cin>>a;
		s1.push_back(a);
	}
	
	for(int i=0;i<m;i++)
	{
		string b;
		cin>>b;
		s2.push_back(b);
	}
	sort(s1.begin(),s1.end());
	sort(s2.begin(),s2.end());
	if(s1.size()>s2.size())
	{
		for(int i=0;i<s2.size();i++)
		{
			if(binary_search(s1.begin(),s1.end(),s2[i])){
				result.push_back(s2[i]);
			}
		}
	}
	if(s1.size()<=s2.size())
	{
		for(int i=0;i<s1.size();i++)
		{
			if(binary_search(s2.begin(),s2.end(),s1[i])){
				result.push_back(s1[i]);
			}
		}
	}
	sort(result.begin(),result.end());
	cout<<result.size()<<'\n';
	for(int i=0;i<result.size();i++)
	{
		cout<<result[i]<<'\n';
	}
	
}

<풀이 과정>

이 문제는 풀 수 있는 방법이 되게 다양하다.

string::npos()를 사용해도 무관하지만 나는 이진 탐색을 이용해 시간복잡도를 줄여서 O(logN)을 통해 풀었다.

우선적으로 듣지도 못한 사람의 벡터 s1

                   보지도 못한 사람의 벡터 s2를 각각 벡터에 넣어준다.

그 이후에 s1과 s2의 길이를 비교해서, 길이가 긴쪽에서 길이가 짧은쪽 벡터에 문자열이 있는지 확인해주면 끝이다.