BOJ 1269 - 대칭 차집합

문제 링크

문제#

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, $A = \{1, 2, 4\}$이고 $B = \{2, 3, 4, 5, 6\}$라고 할 때, $A-B = \{1\}$이고 $B-A = \{3, 5, 6\}$이므로 대칭 차집합의 원소의 개수는 4개이다.

입력#

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력#

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

풀이#

대칭 차집합의 크기는 두 집합에서 공통 원소를 빼고 남는 원소 수다. 그래서 결국 A와 B의 공통 원소가 몇 개인지만 알면 답을 바로 계산할 수 있다.

코드에서는 한쪽 집합을 set이나 map에 넣어 두고, 다른 쪽을 읽으면서 이미 있는지 확인한다. 공통 원소 수를 세었다면 전체 크기에서 두 배를 빼는 식으로 답을 만들 수 있다.

핵심은 원소 자체를 정렬하는 것이 아니라, 포함 여부를 빠르게 확인하는 것이다. membership 조회가 빨라지면 문제는 거의 끝난다.

코드#

#include <iostream>
#include <map>
using namespace std;
 
void solve() {
 
	int n, m, ans = 0, num = 0;
	cin >> n >> m;
	
	map<int, bool> mp;
 
	for (int i = 0; i < n + m; i++) {
 
		cin >> num;
		if (!mp[num]) {
			ans++;
			mp[num] = true;
		}
		else
			ans--;
	}
 
	cout << ans << '\n';
 
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 두 집합의 원소를 삽입하고 조회하므로 정렬 집합 기준 $O((A + B) \log (A + B))$이다.
• 공간 복잡도: 등장한 원소를 map에 저장하므로 $O(A + B)$이다.

마무리#

공통 원소 수만 알면 대칭 차집합 크기는 전체 개수에서 바로 계산된다.