[BaekJoon] #1269 - 대칭 차집합 [Java][C++]

문제 링크

---

1. 아이디어

두 집합 $A$, $B$에 대해 $A - B$와 $B - A$의 합집합인 대칭 차집합을 구하는 문제로 대칭 차집합의 크기는 두 집합의 크기에서 두 집합의 교집합의 크기의 두 배를 빼면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + M)$	$O(N + M)$

($N$ = 입력값 n, $M$ = 입력값 m)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Set<Integer> a = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a.add(Integer.parseInt(st.nextToken()));
        }

        Set<Integer> b = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b.add(Integer.parseInt(st.nextToken()));
        }

        int cnt = 0;
        for (int x : a) {
            if (b.contains(x)) cnt++;
        }

        System.out.println(n + m - 2 * cnt);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

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

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

    int cnt = 0;
    for (int x : a) {
        if (b.count(x)) cnt++;
    }

    cout << n + m - 2 * cnt;
}

---