[백준] 1269번 대칭 차집합 / C++

#문제

백준 1269번 대칭 차집합

#풀이

#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<int> setA;
unordered_set<int> setB;

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

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

	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;

		setA.insert(x);
	}

	for (int i = 0; i < m; ++i)
	{
		int x;
		cin >> x;

		setB.insert(x);
	}

	int cnt = 0;

	for (const int& iter : setA)
	{
		if (setB.find(iter) == setB.end())
		{
			cnt++;
		}
	}

	for (const int& iter : setB)
	{
		if (setA.find(iter) == setA.end())
		{
			cnt++;
		}
	}

	cout << cnt;

	return 0;
}

#정리

두 개 집합의 원소를 받아 각 집합이 공역일 때 차집합 개수를 더하여 출력하는 문제. 배열을 사용하는 경우 시간초과가 발생하여 시간 복잡도가 O(n)인 해쉬맵을 사용하여 해결. if (setB.find(iter) == setB.end()) 인 경우 setA의 모든 원소를 돌면서 setB 내 원소가 없을 경우(setB.find(iter)setB.end()와 같은 경우) 카운팅하는 코드를 작성하였다.




    Enjoy Reading This Article?

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

  • [백준] 1018번 체스판 다시 칠하기 / C++
  • [백준] 1934번 최소공배수 / C++
  • [백준] 15650번 N과 M (2) / C++
  • [백준] 9613번 GCD 합 / C++
  • [백준] 2563번 색종이 / C++