[BackJoon]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을 넘지 않는다.

 

출력

 

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

 

풀이

 

말이 길게 쓰여있지만 요약하면 제목처럼 대칭 차집합을 구하라는 문제이다.

 

나온 김에 정리를 하자면, 대칭 차집합이란 둘 중 한 집합에는 속하지만 나머지 집합에는 속하지 않는 원소들의 모임이다.

 

더 간결한 수학 기호로 대칭 차집합을 표현하면 아래와 같다.

 

$$A \triangle B = (A \setminus B) \cup (B \setminus A)$$

 

이어서 그림으로 위 수식을 표현해 보자.

 

각 집합의 서로에 대한 차집합을 구해서 합치면 될 것처럼 보인다.

 

유효한 생각이지만 다른 길도 있다.

 

바로 합집합에서 교집합을 빼는 것. 어느 쪽이건 연산 횟수는 같으니 취향껏 골라 쓰면 될 것 같다.

 

지난 문제와 이번 문제까지 해서 집합을 이용한 각종 연산에 대해 연습을 시키는 것 같은데,

 

단원이 끝나가고 있으니 전체적으로 정리하는 글을 하나 적어야겠다.

 

일단 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Prob1269_2 {

    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> setN = new HashSet<>();
        Set<Integer> setM = new HashSet<>();

        StringTokenizer stN = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            setN.add(Integer.parseInt(stN.nextToken()));
        }

        StringTokenizer stM = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            setM.add(Integer.parseInt(stM.nextToken()));
        }

        // 합집합
        Set<Integer> union = new HashSet<>(setN);

        union.addAll(setM);

        // 교집합
        Set<Integer> inter = new HashSet<>(setN);

        inter.retainAll(setM);

        // 대칭 차집합
        union.removeAll(inter);

        System.out.println(union.size());
    }
}