[PS] 백준 1269번 대칭 차집합

이번에는 백준 1269번 대칭 차집합 문제를 풀어보았습니다.

대칭 차집합은 두 집합 중 한쪽에만 존재하는 원소들의 집합입니다.

map을 이용하여 같은 원소가 두 번 등장하면 제거하는 방식으로 간단하게 해결할 수 있습니다.

---

문제 설명

두 집합 A, B가 주어집니다.

대칭 차집합은

(A - B) ∪ (B - A)

를 의미합니다.

즉,

한쪽 집합에만 존재하는 원소들

의 개수를 구하는 문제입니다.

---

풀이 아이디어

먼저 집합 A의 모든 원소를 map에 저장합니다.

이후 집합 B를 순회하면서

• 이미 존재하는 원소라면 두 집합 모두에 존재하는 원소이므로 제거합니다.
• 존재하지 않는 원소라면 B에만 존재하는 원소이므로 새롭게 추가합니다.

최종적으로 map에는

A 또는 B 중 한 곳에만 존재하는 원소

만 남게 됩니다.

따라서 map.size()가 정답이 됩니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    map<int, int> m;
    int a,b;
    cin >> a >> b;
    for (int i=0; i<a; i++) {
        int num;
        cin >> num;
        m[num] = 1;
    }
    for (int i=0; i<b; i++) {
        int num;
        cin >> num;
        if (m[num]) {
            m.erase(num);
        } else {
            m[num] = 1;
        }
    }

    cout << m.size() << '\n';

    return 0;
}

---

풀이 흐름

1. 집합 A의 원소를 모두 map에 저장합니다.

2. 집합 B를 하나씩 확인합니다.

3. 현재 원소가 이미 map에 존재한다면 제거합니다.

4. 존재하지 않는다면 새롭게 추가합니다.

5. 모든 입력이 끝난 뒤 map에 남아 있는 원소의 개수를 출력합니다.

---

구현 포인트

1. 집합 A 저장

m[num] = 1;

먼저 A의 모든 원소를 map에 저장합니다.

이 시점에서는

map = A

인 상태입니다.

---

2. 같은 원소 제거

if (m[num]) {
    m.erase(num);
}

B를 탐색하다가 이미 map에 존재하는 원소를 만나면

A와 B 모두에 존재하는 원소

입니다.

대칭 차집합에는 포함되지 않으므로 제거합니다.

예를 들어

A = {1,2,4}
B = {2,3,4}

라면

2, 4

는 제거됩니다.

---

3. 새로운 원소 추가

else {
    m[num] = 1;
}

현재 원소가 map에 없다면

B에만 존재하는 원소

입니다.

따라서 대칭 차집합에 포함되므로 추가합니다.

---

4. 최종 결과

모든 입력이 끝난 뒤 map에는

A에만 있는 원소
+
B에만 있는 원소

만 남게 됩니다.

따라서

m.size()

를 출력하면 대칭 차집합의 원소 개수가 됩니다.

---

5. map을 집합처럼 사용

코드에서는

map<int,int>

을 사용했지만,

실제로는 값은 사용하지 않고

존재 여부

만 확인하고 있습니다.

즉,

set

처럼 활용한 것입니다.

---

시간복잡도

집합 A를 저장하는 데

O(A log A)

집합 B를 처리하는 데

O(B log A)

이 소요됩니다.

따라서 전체 시간복잡도는

O((A + B) log(A + B))

입니다.