[백준] 1269번 대칭 차집합 / C++
#문제
#풀이
#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: