[1269] 대칭 차집합

난이도: ★☆☆☆☆ • solved on: 2026-01-01

---

문제 요약

• 문제 유형: 집합(Set), 해시(Hash)
• 요구사항: 두 집합 A, B에 대해 대칭 차집합 $((A-B) ∪ (B-A))$의 원소 개수를 출력해야 한다.

---

사용 개념

1. 자료구조

   • HashSet : 원소 존재 여부를 평균 O(1)로 검사한다.

2. 알고리즘/기법

   • 집합 연산의 크기 계산
   • 교집합 개수 세기

3. 핵심 키워드

   • 대칭 차집합 (symmetric difference)
   • 교집합 (intersection)

---

풀이 아이디어 및 코드

방법 1 : 합집합을 만들고 교집합 개수만큼 빼기

1. 문제 분해

• A, B를 각각 HashSet에 넣는다.
• A∪B 역할을 하는 setAorB를 만든다.
• setAorB를 순회하며 A와 B에 모두 있으면(교집합) count++ 한다.
• 최종 답을 |A∪B| - |A∩B| 로 계산한다.

2. 핵심 로직 흐름

   setAorB = A ∪ B
   count = |A ∩ B|
   answer = |setAorB| - count

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);
        int count = 0;

        HashSet<String> setA = new HashSet<>(n);
        HashSet<String> setB = new HashSet<>(m);
        HashSet<String> setAorB = new HashSet<>();
        StringTokenizer stA = new StringTokenizer(br.readLine());
        StringTokenizer stB = new StringTokenizer(br.readLine());

        while(stA.hasMoreTokens()){
            String temp = stA.nextToken();
            setA.add(temp);
            setAorB.add(temp);
        }

        while(stB.hasMoreTokens()){
            String temp = stB.nextToken();
            setB.add(temp);
            setAorB.add(temp);
        }

        for(String a : setAorB){
            if(setA.contains(a)&&setB.contains(a)){
                count++;
            }
        }

        System.out.println(setAorB.size()-count);
    }
}

---

방법 2 : 교집합만 세서 n + m - 2*common로 바로 계산

1. 개선 포인트

• 대칭 차집합 크기 = (|A-B| + |B-A|) 이고, 이는 (|A| + |B| - 2|A∩B|) 로 정리된다.
• 따라서 합집합 set을 따로 만들 필요가 없다.

2. 핵심 로직 흐름

   common = 0
   A를 set에 저장
   B를 읽으면서 A에 있으면 common++
   answer = n + m - 2*common

3. 추가 개선

   • 입력이 자연수이므로 HashSet<Integer>로 처리하는 편이 의미상 맞고, 변환 비용도 줄인다.

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

class Main {
    public static void main(String[] args) throws Exception {
        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());

        HashSet<Integer> setA = new HashSet<>(n);

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

        int common = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (setA.contains(x)) common++;
        }

        int answer = n + m - 2 * common;
        System.out.println(answer);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N + M) 평균 (해시 연산 가정)
• 공간 복잡도: O(N + M) (setA, setB, setAorB 저장)

방법 2

• 시간 복잡도: O(N + M) 평균
• 공간 복잡도: O(N) (setA만 유지)

---

어려웠던 점

• 없음

---

배운 점 및 팁

• 대칭 차집합 크기는 $n + m - 2 * |A∩B|$ 로 바로 계산하는 편이 구현과 메모리 측면에서 더 단순하다.
• 이 문제는 최대 200,000개 원소까지 가능하므로, 이중 루프 대신 해시 기반 포함 검사로 풀어야 한다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/1269
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 14425번 문자열 집합
  • 백준 - 1764번 듣보잡
  • 백준 - 7785번 회사에 있는 사람
  • 백준 - 10816번 숫자 카드 2

• 확장 문제 (GPT 추천):

  • HackerRank - No Idea!
  • HackerRank - Two Strings