[백준 1269] 대칭 차집합

문제출처: https://www.acmicpc.net/problem/1269

입력받는 수의 갯수가 최대 20만개이므로 정렬 연산 시 최악의 경우 4억번(약 4초) 연산을 할 수 있으므로

O(nlogn)의 효율적인 알고리즘을 써야합니다. 퀵 소트는 최악의 경우 O(n^2)이므로 통과가 안 될 수 있음을 유념합니다.

정렬 알고리즘 시간복잡도 및 분석: https://jow1025.tistory.com/20

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 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 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

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

출력

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

풀이

1. 차집합을 계산하기 위해 두 집합을 오름차순 정렬합니다.

( 이 때 시간복잡도가 O(nlogn)으로 안정적인 병합정렬을 사용합니다.

2. a집합과 b집합의 차집합 후 원소의 갯수는 각각 a와 b의 집합의 총 원소의 갯수에서 겹치는 수를 제외한 나머지 원소의 갯수입니다.(정답)

3. 병합정렬 후 A집합과 B집합에서 겹치는 원소의 개수를 찾아낸 뒤 정답을 출력합니다.

코드

#include<iostream>
using namespace std;
int a[200001], b[200001];
using namespace std;
void merge(int a[], int start, int end);
void merge_sort(int a[], int start, int middle, int end);
int sorted[200001];
int main()
{
	int n, m;
	cin >> n >> m;
	cin.tie(0);//시간을 줄이기위해 선언
	cin.sync_with_stdio(false);//시간을 줄이기위해 선언
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	merge(a, 0, n - 1);
	merge(b, 0, m - 1);
	//정렬되어있는 상태
	int a_start = 0, b_start = 0;
	int cnt = 0;
	//a-b차집합의 원소갯수: a의전체원소 수 - 겹치는 수의 갯수
	//b-a차집합의 원소갯수: b의전체원소 수 -겹치는 수의 갯수
	while (a_start < n && b_start < m)
	{
		if (a[a_start] == b[b_start])
			a_start++, b_start++, cnt++;
		else if (a[a_start] < b[b_start])
			a_start++;
		else
			b_start++;
	}
	cout << (n - cnt) + (m - cnt) << endl;
}
void merge(int a[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge(a, start, middle);
		merge(a, middle + 1, end);
		merge_sort(a, start, middle, end);
	}
}
void merge_sort(int a[], int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int k = start;
	while (i <= middle && j <= end)
	{
		if (a[i] <= a[j])
			sorted[k++] = a[i++];
		else
			sorted[k++] = a[j++];
	}
	if (i > middle) {
		for (int l = j; l <= end; l++)
			sorted[k++] = a[l];
	}
	else
	{
		for (int l = i; l <= middle; l++)
			sorted[k++] = a[l];
	}
	for (int l = start; l <= end; l++)
		a[l] = sorted[l];
}

결과