백준 1764 듣보잡(c++)

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

1764번: 듣보잡

<틀린 코드>

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

int main()
{
	int n,m;
	cin>>n>>m;
	string str1,str2;
	vector<string>s1;
	vector<string>s2;
	vector<string>result;
	vector<string>::iterator iter;
	for(int i=0;i<n;i++)
	{
		cin>>str1;
		s1.push_back(str1);
	}
	for(int i=0;i<m;i++)
	{
		cin>>str2;
		s2.push_back(str2);
	}
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s1[i]==s2[j])
			{
				cnt++;
				result.push_back(s1[i]);	
			}	
		}	
	}
	sort(result.begin(),result.end());
	cout<<cnt<<'\n';
	for(auto iter = result.begin();iter!=result.end();iter++)
	{
		cout<<(*iter)<<'\n';
	}
}

테스트케이스에서 될 수 있는 n,m의 값이 각각 50만이기 때문에 이중 포문을 돌리면 시간 초과가 뜨게 된다.

그래서 할 수 있는 방법이 map 헤더를 이용하는 것이다.

<맞는 코드>

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

int main()
{
	int n,m;
	cin>>n>>m;
	string str;
	map<string,int>mm;
	vector<string>v;
	vector<string>::iterator iter;
	for(int i=0;i<n+m;i++)
	{
		string str;
		cin>>str;
		mm[str]++;
		if(mm[str]>1) v.push_back(str);
	}
	
	sort(v.begin(),v.end());
	cout<<v.size()<<'\n';
	for(auto iter = v.begin();iter!=v.end();iter++)
	{
		cout<<(*iter)<<'\n';
	}
}

<풀이과정>

map헤더를 이용하여 mm에 있는 str의 key값이 1보다 크면(2개 이상)이면 벡터에 문자열을 push해준다.