백준 1764 듣보잡

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 듣과 보각각 문자열을 입력받고 둘다 해당하는 경우의 수와 문자열을 출력하는 문제입니다.

 

각각의 경우가 500000 까지 가능하므로 그냥 두 문자열을 비교하면 O(N^2)으로 시간 초과가 날 것입니다.

 

따라서 저는 multiset과 set을 이용해서 처음에 multiset에 문자열을 모두 입력받고 멀티셋의 카운트가 2인 문자열을 다시 셋에 집어넣었습니다.

 

코드입니다.

 

#include <iostream>
#include <string>
#include <set>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	int num = 0;
	cin >> N >> M;
	multiset <string> ms;
	string str;
	set<string> s;
	
	for(int i = 0; i < N; i++) { //multiset에 듣과 보의 입력을 받음 
		cin >> str;
		ms.insert(str);
	}
	for(int i = 0; i < M; i++) {
		cin >> str;
		ms.insert(str);
	}
	
	for(auto it: ms) { //multiset에 2번 저장된 문자열을 set에 집어넣음 
		if(ms.count(it) == 2) {
			s.insert(it);
			num++;	
		}
	}
	
	cout<<num/2<<'\n'; //카운트는 2번씩 되었으니 2로 나누어줌 
	for(auto n: s)
		cout<<n<<'\n';
		
	return 0;
}