[Baekjoon Online Judge] 1822. 차집합 (Java)

핵심

두 배열의 길이가 500,000이다.

따라서 배열 A의 각 원소가 배열 B의 원소에 포함되어 있는지 일일이 확인한다면 시간복잡도는 O(N^2)이 된다. (시간 초과)

 

따라서 시간복잡도를 줄여야 한다.

원소가 많은 배열에서 특정한 원소가 포함되어 있는지 확인해야하는 문제이다.
이분 탐색에 대해 알고 있다면 대부분 쉽게 떠올릴 수 있을 것이다. (모르겠다면 이분 탐색, 3분 안에 이해하기 참고)
그럼 시간복잡도는 O(NlogN)으로 줄고 여유있게 풀 수 있다.

Code (Java)

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

import static java.util.Collections.binarySearch;

public class Main {

    public static void main(String[] args) throws IOException {

        StringBuilder sb = new StringBuilder();
        Scanner sc = new Scanner(System.in);

        int nA = sc.nextInt();
        int nB = sc.nextInt();

        List<Integer> arrA = new ArrayList<>();
        List<Integer> arrB = new ArrayList<>();


        for (int i = 0; i < nA; i++) {
            int val = sc.nextInt();
            arrA.add(val);
        }

        for (int i = 0; i < nB; i++) {
            int val = sc.nextInt();
            arrB.add(val);
        }

        Collections.sort(arrB);

        List<Integer> diffSet = new ArrayList<>();
        for (Integer elem : arrA) {
            if (binarySearch(arrB, elem) < 0) {
                diffSet.add(elem);
            }
        }

        Collections.sort(diffSet);

        sb.append(diffSet.size()).append('\n');
        for (int elem : diffSet) {
            sb.append(elem).append(' ');
        }
        System.out.println(sb);
    }
}