[백준 1269번] 대칭 차집합

소스코드

---

#include <iostream>
using namespace std;
 
int na, nb, a[200001], b[200001], tmp[200001], r=0;
 
void merge(int arr[], int start, int mid, int end) {
    int lidx = start, tmpidx = 0, ridx = mid + 1;
 
    while (lidx <= mid&&ridx <= end) {
        if (arr[lidx] < arr[ridx])
            tmp[tmpidx] = arr[lidx++];
        else
            tmp[tmpidx] = arr[ridx++];
        tmpidx++;
    }
 
    while (lidx <= mid)
        tmp[tmpidx++] = arr[lidx++];
    while (ridx <= end)
        tmp[tmpidx++] = arr[ridx++];
 
    tmpidx = 0;
    for (int i = start; i <= end; i++)
        arr[i] = tmp[tmpidx++];
}
 
void merge_sort(int arr[], int start, int end) {
    if (start == end)
        return;
    int mid = (start + end) / 2;
    merge_sort(arr, start, mid);
    merge_sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> na >> nb;
    for (int i = 0; i < na; i++)
        cin >> a[i];
    for (int i = 0; i < nb; i++)
        cin >> b[i];
    merge_sort(a, 0, na - 1);
    merge_sort(b, 0, nb - 1);
 
    int aidx=0, bidx=0;
    while (aidx < na && bidx < nb) {
        if (a[aidx] == b[bidx])
            r++,aidx++,bidx++;
        else if (a[aidx] < b[bidx])
            aidx++;
        else if (a[aidx] > b[bidx])
            bidx++;
    }
    cout << (na-r) + (nb-r) << '\n';
    return 0;
}