99클럽 코테 스터디 7일차 TIL [BOJ] 대칭 차집합 (Java)

문제

[BOJ] 대칭 차집합

틀린 코드

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

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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        Set<Integer> answer = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            B.add(Integer.parseInt(st.nextToken()));
        }
        for(int x : A) {
            if(!B.contains(x)) {
                answer.add(x);
            }
        }
        for(int x : B) {
            if(!A.contains(x)) {
                answer.add(x);
            }
        }
        System.out.print(answer.size());
    }
}

틀린 이유

• List의 contains()는 O(n)의 시간 복잡도를 가져 시간 초과 발생

풀이

• A와 B를 리스트가 아닌 HashSet을 사용하면 O(1)의 시간 복잡도를 가져 효율성 증가한다.
• A와 B의 요소를 탐색해 서로 포함하지 않는 요소를 answer에 추가한다.

정답 코드

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

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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Set<Integer> A = new HashSet<>();
        Set<Integer> B = new HashSet<>();
        Set<Integer> answer = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            B.add(Integer.parseInt(st.nextToken()));
        }
        for(int x : A) {
            if(!B.contains(x)) {
                answer.add(x);
            }
        }
        for(int x : B) {
            if(!A.contains(x)) {
                answer.add(x);
            }
        }
        System.out.print(answer.size());
    }
}