[백준] 1269 대칭 차집합 - HashSet(해시셋) JAVA

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

1269번: 대칭 차집합

코드설명

HashSet을 활용합니다.

 

최악의 경우 각 집합의 원소의 개수는 200,000 입니다.

만약, 200,000 * 200,000 = 400억입니다.

 

Hashset을 활용해서 시간복잡도를 단 O(n + k) = O(200,000 + 200,000) = O(400,000)으로 만들 수 있습니다

HashSet_A의 값이 HashSet_B이 없는지 찾는경우를 단순히 O(1)에 조회할 수 있고, HAshSet_A의 Size가 200,000 이므로 위의 시간복잡도 가 나옵니다.(Hashset_B도 반대로 마찬가지입니다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class Main {
	public static int N, K;
	public static HashSet<Integer> HashSetA = new HashSet<Integer>();
	public static int answer = 0;
	
	public static HashSet<Integer> hashset_A = new HashSet<>();
	public static HashSet<Integer> hashset_B = new HashSet<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

	    st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			int a = Integer.parseInt(st.nextToken());
			hashset_A.add(a);
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<K;i++) {
			int a = Integer.parseInt(st.nextToken());
			hashset_B.add(a);
		}
		
		for(int a : hashset_A) {
			if(!hashset_B.contains(a)) {
				answer += 1;
			}
		}
		for(int a : hashset_B) {
			if(!hashset_A.contains(a)) {
				answer += 1;
			}
		}
		System.out.println(answer);
	}
}