[백준] 14425번 - 문자열 집합

www.acmicpc.net

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

문제

💡

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

시간 제한: 2초

메모리 제한: 1536MB

입력

💡

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

💡

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

예제 입력	예제 출력
`5 11 baekjoononlinejudge startlink codeplus sundaycoding codingsh baekjoon codeplus codeminus startlink starlink sundaycoding codingsh codinghs sondaycoding startrink icerink`	4

풀이

문자열 집합 S에 포함된 N개의 문자열과 M개의 문자열을 하나씩 직접 비교하면, 문자열의 최대 길이가 500이므로 1e4 × 1e4 × 5e2 = 5e10번의 연산이 발생해 약 500초가 걸리게 된다. 이는 시간 제한을 초과한다.

처음에는 집합을 정렬한 뒤 이진 탐색을 이용하는 방법을 생각했지만, 문자열 문제에서는 이보다 더 빠르고 간단한 방법이 있을 것 같아 다른 방식을 고민해보았다.

그때 떠올린 방법이 바로 탐색 속도가 빠른 해시 테이블을 이용하는 것이었다. 이번 문제에서는 각 문자열이 집합에 존재하는지만 확인하면 되므로, value가 필요 없는 unordered_set을 사용했다.

unordered_set은 이번에 처음 사용해 봤는데, 문법이 간단하고 응용하기도 쉬워서 이런 문자열 집합 문제에서 앞으로 자주 활용해야겠다고 느꼈다.

코드


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

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

	int N, M;
	cin >> N >> M;

	unordered_set<string> S;
	for (int i = 0; i < N; ++i) {
		string tmp;
		cin >> tmp;
		S.insert(tmp);
	}

	int ans = 0;

	for (int i = 0; i < M; ++i) {
		string tmp;
		cin >> tmp;
		if (S.find(tmp) != S.end()) {
			ans += 1;
		}
	}

	cout << ans;

	return 0;
}