25. UVa-11849 CD

문제

<그림1: 문제 설명>

중복 원소 개수 세는 문제

input이 ascending order로 되어있어서 set의 find에 걸리는 logN시간이 낭비같아서 N개의 input 배열에 대해서 index 두개 두고 하려니 상당히 overhead가 많다(물론 const겠지만) 그리고 솔직히 귀찮다. 코드는 다음과 같다.

 

#include<iostream>
#include<set>
using namespace std;

int main() {
	//N+MlgN solution
	int N, M,temp,sum;
	while (cin >> N >> M) {
		if (N == 0 && M == 0) break;
		sum = 0;
		set<int> catalogs;
		for (int i = 0; i < N; i++) {
			cin >> temp;
			catalogs.insert(temp);
		}
		for (int j = 0; j < M; j++) {
			cin >> temp;
			if (catalogs.find(temp) != catalogs.end()) ++sum;
		}
		cout << sum<<endl;
	}

	return 0;
}