백준 1269: 대칭 차집합(java)

문제

---

풀이

 

대칭 차집합은 (A의 원소 개수) + (B의 원소 개수) - 2*(A, B 교집합의 원소 개수) 로 구할 수 있으므로 이를 이용해 풀이한다. A와 B 교집합의 원소 개수를 구하기 위해 이진 탐색을 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int aCount=Integer.parseInt(st.nextToken());	//A 원소 개수
		int bCount=Integer.parseInt(st.nextToken());	//B 원소 개수
		
		st=new StringTokenizer(br.readLine());
		int[] aArr=new int[aCount];
		for(int i=0; i<aCount; i++) {
			aArr[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(aArr);
		
		st=new StringTokenizer(br.readLine());
		int[] bArr=new int[bCount];
		for(int i=0; i<bCount; i++) {
			bArr[i]=Integer.parseInt(st.nextToken());
		}
		
		int intersection=0;	//교집합
		for(int i=0; i<bCount; i++) {	//이진 탐색
			int bin=Arrays.binarySearch(aArr, bArr[i]);
			if(bin>-1)
				intersection++;
		}
		
		int sdc=aCount+bCount-intersection*2;	//대칭차집합
		System.out.println(sdc);
	}
}