백준 - 대칭 차집합( 1269번, JAVA )

Hash ( https://www.acmicpc.net/problem/1269 )

풀이

• 각각의 A와 B를 Hash에 입력
• hash는 get메소드가 없기 때문에 Hash를 상속 받은 ArrayList를 선언하면서 바로 삽입
• A와 B 각각 (A-B) (B-A) 각각 포함되지 않는다면 answer 카운트 해줬다

기억해야할 것

• 처음에 ArrayList에 contains를 사용하니까 시간초과가 나왔다
• HashSet contains 메소드의 시간복잡도는 일반적으로 O(1) 으로 상당히 빠르다.
• ArrayList contains 메소드의 시간복잡도는 일반적으로 O(n) 으로 요소의 수에 따라 다르다.
• 근데 여기서 궁금한 게 크기가 똑같다는 전제하인데 ?
  -> ArrayList는 순차적으로 찾고 HashSet은 내부적으로 해시값으로 값을 찾기 때문
• 쉬운 문제여도 시간복잡도를 항상 고려하자

package problem_solving.hash;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class BaekJoon_1269 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashSet<Integer> h1 = new HashSet<>();
		HashSet<Integer> h2 = new HashSet<>();
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int answer =0 	 ;
		for(int i= 0 ; i < n ; i++) {
			h1.add(Integer.parseInt(sc.next()));
		}
		ArrayList<Integer> list1 = new ArrayList<>(h1);
		for(int i= 0 ; i < m ; i++) {
			h2.add(Integer.parseInt(sc.next()));
		}
		ArrayList<Integer> list2 = new ArrayList<>(h2);
		
		for(int i= 0 ; i < list1.size() ; i++) {
			int num = list1.get(i);
			if( !h2.contains(num)) {
				answer++;
			}
		}
		for(int i= 0 ; i < list2.size() ; i++) {
			int num = list2.get(i);
			if( !h1.contains(num)) {
				answer++;
			}
		}
		
		
		
		System.out.println(answer);
		
		
		
		
	}

}