[알고리즘] 백준 1269 - 대칭 차집합

1. 문제

https://www.acmicpc.net/problem/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개이다.

2. 입력

첫째 줄 : A의 원소의 개수, B의 원소의 개수
둘째 줄 : A의 원소
셋째 줄 : B의 원소

3. 풀이

풀이 자체는 쉬운데 시간 초과가 중요한 문제였다.
처음에는 Scanner랑 Arraylist를 이용해서 풀었는데 시간 초과가 떠서 다음과 같은 방법으로 바꿨다.

1) BufferedReader
데이터를 한번에 읽어와 버퍼에 보관한 후, 요청이 있을 때에 버퍼에서 데이터를 읽어온다.
따라서 Scanner보다 훨씬 속도가 빠르고 시간 부하가 적다.
String 형식으로 인식하기 때문에 형변환이 필수

2) Set
Arraylist의 경우 순서를 함께 저장하고 탐색하는데 시간이 오래 걸린다.
Set은 데이터를 중복해서 저장할 수 없고 순서가 보장되지 않는다.
해당 문제는 집합이므로 순서를 저장할 필요가 없고, 탐색에 유리한 Set을 사용하면 시간을 줄일 수 있다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class symmetricDifference {
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        //각 집합의 원소 개수
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        //대칭차집합을 저장할 set
        Set<Integer> set = new HashSet<>();

        //A원소 set에 저장
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<A;i++){
            set.add(Integer.parseInt(st.nextToken()));
        }

        int tmp;
        int count=0; //교집합 원소 개수

        //A와 겹치지 않는 원소 저장
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<B;i++){
            tmp = Integer.parseInt(st.nextToken());
            //교집합에 해당하는 원소 개수 카운트
            //집합에서 remove로 제거해도 되지만 빨리할려고 카운트 세서 빼줬음
            if(set.contains(tmp)){
                count++;
            }
            else{
                set.add(tmp);
            }
        }

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

'''