[1269번] 대칭 차집합

www.acmicpc.net/problem/1269

1269번: 대칭 차집합

풀이

대칭 차집합의 성질을 이용하여 문제를 해결할 수 있습니다.
* (대칭 차집합) = (A-B) U (B-A)

결론적으로 대칭 차집합이란 두 개의 집합을 두고 보았을 때, 서로 겹치는 원소를 제외한 나머지가 됩니다.

이러한 대칭 차집합의 정의와 map 자료구조의 중복된 원소는 저장하지 않는 성질을 이용하여 문제를 풀었습니다.

 

1.  a+b만큼 for문을 순회하며 원소를 입력받고,
2. mp(map)에 존재하지 않는 원소라면 (mp.count(x) == 0) mp에 저장하고
3. mp에 존재하는 원소라면 mp에서 원소를 삭제해줍니다.

마지막으로 mp의 사이즈를 출력해주어 문제를 해결할 수 있습니다 !

전체 코드

#include <iostream>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int a, b;
	cin >> a >> b;
	map<int, int> mp;
	for (int i = 0;i < a + b;i++) {
		int x;
		cin >> x;
		if (mp.count(x) == 0) mp[x] = 1;
		else mp.erase(x);
	}
	cout << mp.size() << "\n";
}