풀이 아이디어

HashSet
Java 자료구조 HashSet을 사용해서
특정 키가 있는지 평균 O(1)시간만에 탐색할 수 있도록 하였고
A리스트의 원소를 입력받는대로 전부 HashSet의 키를 저장한 다음
B리스트의 원소를 입력받으면서
HashSet에 이미 있는 키인 경우 제거한다.
겹치지 않는 원소는 HashSet에 추가한다.
마지막에 HashSet의 사이즈를 출력하면 답이다.

오답 코드

처음에는 대칭차집합 원소의 개수를 세는 변수
int totalCount를 A 리스트의 원소 개수로 저장하고
ArrayList에 A 리스트의 원소를 모두 저장하고
B 원소를 입력받으면서 중복된 원소가 나오면 totalCount-1해줬다.
겹치지 않으면 totalCount+1해주고
최종 대칭차집합 원소의 개수 totalCount를 출력한다.

ArrayList로 하나의 원소마다 값을 확인하기위해 탐색을 하다보니
시간초과가 발생했다.
예를 들어 원소가 20만개면
'10000'값을 찾기 위해 1~10000까지 만 번을 탐색해야할 수 있어서 시간초과가 발생했다.
그래서 특정 숫자가 존재하는지는 탐색하는 시간이 O(N)이 되었다.

import java.util.*;
import java.io.*;
public class _1269 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int aSize = Integer.parseInt(st.nextToken());
        int bSize = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> aList = new ArrayList<>();
        int input;
        int totalCount = 0;
        for(int i=0;i<aSize;i++){
            input = Integer.parseInt(st.nextToken());
            aList.add(input);
        }
        totalCount = aList.size();
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<bSize;i++){
            input = Integer.parseInt(st.nextToken());
            if(aList.contains(input)){
                totalCount--;
            }
            else{
                totalCount++;
            }
        }
        System.out.println(totalCount);
    }
}

정답 코드

HashSet은 중복되지 않은 특정 키만 있는지 확인해서
바로 확인해서 평균 탐색시간이 O(1)이 된다.
왜 그런지 확인해보니 HashSet은 HashTable기반으로
HashSet 입력값을 HashTable 특정 인덱스에 값을 매핑해서 저장하는데
입력값을 입력으로 해시함수 리턴값이 해시테이블의 인덱스가 되고
해시함수 실행시간이 상수시간이기 때문에 평균 탐색시간이 O(1)이 나오게된다.

import java.util.*;
import java.io.*;
public class _1269 {
    public static void main(String[] args) throws IOException{
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int aSize = Integer.parseInt(st.nextToken());
        int bSize = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        HashSet<Integer> hashSet = new HashSet<>();
        for(int i=0;i<aSize;i++){
            hashSet.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<bSize;i++){
            int input = Integer.parseInt(st.nextToken());
            // A와B가 겹치면 제거
            if(hashSet.contains(input)){
                hashSet.remove(input);
            }
            // A와 겹치지 않는 B원소는 추가
            else{
                hashSet.add(input);
            }
        }
        // 대칭 차집합 원소 수 출력
        System.out.println(hashSet.size());
    }
}