1269번: 대칭 차집합

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있습니다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하는 문제입니다. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 합니다.

• 입력: 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈칸을 사이에 두고 주어집니다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈칸을 사이에 두고 각각 주어집니다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않습니다.
• 출력: 첫째 줄에 대칭 차집합의 원소의 개수를 출력합니다.

링크: https://www.acmicpc.net/problem/1269

풀이: HashSet과 집합의 성질을 활용한 탐색

주어진 두 집합의 대칭 차집합의 크기를 구하는 문제입니다. 두 집합의 크기가 최대 200,000이므로, 배열을 이용한 이중 반복문 완전 탐색은 시간 초과가 발생할 수 있습니다. 따라서 탐색 속도가 빠른 HashSet을 활용합니다.

• 데이터 저장: 집합 A와 집합 B의 원소들을 각각 HashSet(setA, setB)에 저장하여 중복을 제거하고 빠른 탐색을 준비합니다.
• 교집합 크기 계산: 집합 A의 원소들을 순회하며 해당 원소가 집합 B에도 존재하는지 contains() 메서드로 확인합니다. 존재한다면 교집합의 원소이므로 cnt를 1 증가시킵니다.
• 대칭 차집합 계산: 대칭 차집합의 크기는 전체 합집합의 크기에서 교집합을 뺀 것과 같습니다. 이는 수식으로 |A| + |B| - 2 * |A ∩ B| 와 동일합니다. 코드에서는 setA.size() + setB.size() - 2 * cnt를 계산하여 대칭 차집합의 개수를 도출합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());
       Set<Integer> setA = new HashSet<>();
       Set<Integer> setB = new HashSet<>();

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

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

       int cnt = 0;
       for (int i : setA) {
          if (setB.contains(i)) {
             cnt++;
          }
       }

       bw.write((setA.size() + setB.size() - 2 * cnt) + "");

       bw.flush();
    }
}

알고리즘 분류

자료 구조 (Data Structures), 해시를 사용한 집합과 맵 (Hash Set/Map)