Baekjoon 1269 대칭 차집합 JAVA

 

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

출력

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

풀이

이 문제는 Boolean 배열을 이용하는 방법으로도 해결 할 수 있는 문제이다.

다만 원소의 값이 100,000,000까지 나올 수 있기에 효율적인 형태가 아니다.

 

본인은 HashSet을 이용하여 문제를 해결하였다.

 

문제에서 요구하는 대칭 차집합은 (A⋃B) - (A∩B)의 값을 찾는 것이다.

이 형태를 찾기 위해서는 A에는 존재하면서 B에는 없는, 동시에 B에는 존재하지만 A에는 없는 원소를 찾아주면된다.

 

1. 집합 A에 존재하는 원소들의 값을 HashSet에 추가하여준다.

2. 집합 B를 입력받으면서 이미 존재하면 HashSet에서 삭제를 하고, 존재하지 않는다면 HashSet에 추가를 한다.

3. 최종적으로 A혹은 B에만 존재하는 원소가 HashSet에 추가되어 있다.

4. HashSet에 존재하는 원소들의 개수를 출력하면 문제에서 요구하는 답이 나온다.

코드

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

public 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 an=Integer.parseInt(st.nextToken()), bn=Integer.parseInt(st.nextToken()), ans=0;
		HashSet<Integer> A = new HashSet<Integer>();
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<an;i++)
			A.add(Integer.parseInt(st.nextToken()));
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<bn;i++) {
			int temp=Integer.parseInt(st.nextToken());
			if(A.contains(temp))
				A.remove(temp);
			else
				A.add(temp);
		}
		System.out.println(A.size());
	}
}