문제출처: 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];
}
결과
