수 찾기

풀이

처음에 배열에서 수를 찾는 문제이므로 이분 탐색으로 해야 겠다 싶어서 N의 최댓값을 봤더니 100,000이었습니다. 원래 이분 탐색의 시간 복잡도는 $O(\log N)$이지만 잠깐 착각해서 $O(N\log N)$으로 생각하고 문제를 풀었습니다. 그래서 이분 탐색이 아닌 두 배열을 정렬해서 비교하는 식으로 풀었습니다.

구현

import java.util.*;

public class Main {

    public static int N, M;
    public static int[] A, B, C;
    public static HashMap<Integer, Integer> map = new HashMap<>();

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        Arrays.sort(A);
        M = scanner.nextInt();
        B = new int[M];
        for (int i = 0; i < M; i++) {
            B[i] = scanner.nextInt();
        }
        C = Arrays.copyOf(B, B.length);
        Arrays.sort(C);
    }

    public static void solve() {
        int indexA = 0;
        for (int i = 0; i < M; i++) {
            boolean finish = false;
            while (indexA < A.length && A[indexA] < C[i]) indexA++;
            if (indexA >= A.length) finish = true;
            if (finish == true || A[indexA] != C[i]) {
                map.put(C[i], 0);
            } else {
                map.put(C[i], 1);
            }
        }
    }

    public static void output() {
        for (int i : B) {
            System.out.println(map.get(i));
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int tc = 1;
        for (int i = 1; i <= tc; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

이렇게 풀고 보니 조금 깨끗하게 푼 것 같지 않아서 다른 사람들이 푼 것을 확인해보니 이분 탐색으로 풀었다는 것을 보고 시간 복잡도를 착각했다는 것을 알았습니다.

import java.util.*;

public class Main {

    public static int N, M;
    public static int[] A;
    public static int[] result;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        Arrays.sort(A);
        M = scanner.nextInt();
        result = new int[M];
        for (int i = 0; i < M; i++) {
            int num = scanner.nextInt();
            if (Arrays.binarySearch(A, num) >= 0) result[i] = 1;
            else result[i] = 0;
        }
    }

    public static void solve() {

    }

    public static void output() {
        for (int i : result) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int tc = 1;
        for (int i = 1; i <= tc; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

이분 탐색으로 풀면 매우 깔끔하다.