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 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

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

출력

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

내 접근

집합에서 요소는 중복되지 않는다고 알고 있는데, std::set을 쓸 수 있을까? 순서는 의미가 없어보이니 std::unordered_set을 사용할 수 있겠다.
출력은 집합 A와 B간 대칭 차집합의 원소 개수를 물어보고 있네, 원소 값이 무엇인지는 중요하지 않은 것 같으니 set을 사용한다면 find를 사용할 필요 없이 count만 사용해도 되겠다.
각 집합의 원소 개수는 최대 2 x 10^5 이고 집합 A의 크기는 n이고, 집합 B의 크기는 m이니까. std::set을 사용한다면, A - B를 구할 때는 O(m log n) 이고, B - A를 구할 때는 O(n log m)이 되는건가? 이걸 합치면 이 문제의 전체 시간 복잡도를 O((n + m) log (n + m))이라고 할 수 있는건가? std::unordered_set을 사용한다면 어떻지? count의 평균 시간 복잡도는 O(1)인데, 그러면 A - B를 구할 때는 O(n)이고, B - A를 구할 때는 O(m)이니까, 전체 시간 복잡도는 O(n + m)인가?

구현

#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#include <unordered_set>

void solve() {
  int n, m;
  std::cin >> n >> m;

  std::unordered_set<int> a;
  std::unordered_set<int> b;
  a.reserve(n);
  b.reserve(m);

  int x;
  for (int i = 0; i < n; i++) {
    std::cin >> x;
    a.insert(x);
  }

  for (int i = 0; i < m; i++) {
    std::cin >> x;
    b.insert(x);
  }

  int sum = 0;
  for (const auto &it : a) {
    if (b.count(it) == 0)
      sum++;
  }

  for (const auto &it : b) {
    if (a.count(it) == 0)
      sum++;
  }

  std::cout << sum;
}

int main() {
  IO;
  solve();
  return 0;
}

다른 접근 방법들

정렬 후 투 포인터

두 집합을 각각 정렬
각 집합의 원소를 가리키는 포인터
1. 포인터 두 개의 원소가 같으면 skip (두 포인터 모두 다음 원소로 이동)
2. 만약 작은쪽이 있으면 카운트 증가 시키고, 작은 쪽 포인터만 증가

sort A, sort B
i = j = 0
while i < n and j < m:
  if A[i] == B[j]: i++, j++
  else if A[i] < B[j]: count++, i++
  else: count++, j++
count += (n - i) + (m - j)

해시 맵에서 XOR 토글

모든 원소를 단일 입력처럼 처리
원소 입력마다 해시 맵의 상태를 토글

map<int, bool> seen
for x in A: seen[x] = !seen[x]
for x in B: seen[x] = !seen[x]
count = number of true values