백준 4158

백준 4158 : CD

1. set이 자동으로 정렬되고, find가 O(1)에 수행되는 점을 이용해 set으로 풀이 하였다.
2. 이랬더니 시간 초과가 났다.
3. set의 시간복잡도는 O(logN), 따라서 더 작은 시간 복잡도인 O(1)을 가지는 undered_set을 이용했더니 맞았다.

정답 코드

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n=1, m=1;
	while(1) {
		cin>>n>>m;
		if(n==0 && m==0) {
			break;
		}		
	
		unordered_set<int> s;
		
		int cnt=0;
		
		for(int i=0; i<n; i++) {
			int temp;
			cin>>temp;
			s.insert(temp);
		}
		for(int i=0; i<m; i++) {
			int temp;
			cin>>temp;
			if(s.find(temp)!=s.end()) {
				cnt++;
			}
		}
		
		cout<<cnt<<'\n';
	}

	
    return 0;
}

map : 정렬이 됨, O(logN)
unordered_map : 정렬이 안됨, 최소 O(1), 최악의 경우 O(N)