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

#문제

백준 14425번 문자열 집합

#풀이

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

unordered_set<string> strs;

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

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

	while (n--)
	{
		string str;
		cin >> str;

		strs.insert(str);
	}

	int cnt = 0;

	while (m--)
	{
		string str;
		cin >> str;

		if (strs.find(str) != strs.end())
		{
			cnt++;
		}
	}

	cout << cnt;

	return 0;
}

#정리

n개의 문자열을 입력받고, m개의 문자열을 입력받는다. 중복되는 문자열이 몇개인지 출력하는 문제. 첫 시도에서는 간단하게 vector 컨테이너를 사용하여 for문으로 문자열을 찾았다. 시간초과. O(1)의 시간 복잡도로 원소를 찾을 수 있는 해쉬셋을 이용하여 해결.




    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • [백준] 1764번 듣보잡 / C++
  • [백준] 18258번 큐 2 / C++
  • [백준] 1269번 대칭 차집합 / C++
  • [백준] 11651번 좌표 정렬하기 2 / C++
  • [백준] 17219번 비밀번호 찾기 / C++