[c++/백준] 14425 문자열 집합

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

14425번: 문자열 집합

생각보다 간단하게 풀렸던 것 같다. 

입력값의 범위가 N, M 모두 최대 10,000이기 때문에 최악의 경우 10의 8승까지 나오게 될 것 같아서 겁 먹고 시작했지만 간단하게 풀렸다. 

 

2중 for문을 사용하면 시간초과가 될 것이기에 신경쓰면서 풀었던 것 같다. 

 

vector를 사용하면 시간초과가 나기 때문에 set을 사용하는 것이 좋을 것 같다. 

그냥 set을 사용해도 되지만 난 그냥 시간복잡도 최소화하기 위해 unordered_set을 사용하였다.

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	unordered_set<string> s;  //시간 복잡도 최대한 줄이기 위함

	for (int i = 0; i < n; i++) {
		string x;
		cin >> x;
		s.insert(x);
	}
	int cnt = 0;
	while (m--) {
		string str;
		cin >> str;
		
		if (s.find(str) == s.end()) //s 안에 str이 없으면 continue
			continue;
		else                        //있으면 cnt++;
			cnt++;
	}
	
	cout << cnt;
	return 0;
}

실제로 set과 unordered_set의 시간 차이가 조금 나는 것을 볼 수 있음.

 

컴파일에러는 vector find 사용할 때 #include <algorithm> 안해서 ㅎ,,,