[백준 c++] 1269 대칭 차집합

문제

https://www.acmicpc.net/problem/1269
두 집합이 주어졌을 때 대칭 차집합을 구하는 문제다.
두 집합끼리 겹치는 원소 제외한 나머지 원소들의 개수 구하면 된다.

풀이

이분탐색으로 a원소들을 순회하면서 해당 원소가 b집합 내 원소와 겹치면 cnt를 증가시킨다.
결과는 a집합 크기 + b집합 크기 -(cnt*2)를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int t, n, m, res;
int main()
{
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++)
    {
        int hi = m - 1, lo = 0;
        while (lo <= hi)
        {
            int mid = (hi + lo) / 2;
            if (a[i] == b[mid])
            {
                res++;
                break;
            }
            if (a[i] > b[mid])
                lo = mid + 1;
            else if (a[i] < b[mid])
                hi = mid - 1;
        }
    }
    cout << a.size() + b.size() - (res * 2) << "\n";
    return 0;
}