[백준] 1920번 - 수 찾기 (Silver 4)

문제 링크

백준 1920번 - 수 찾기 (Silver 4)

문제 설명

입력받은 M개의 정수가 먼저 입력받은 N개의 정수 중에 있는지를 찾는 문제

주의점

• 시간복잡도에 유의해야한다.
  • $O(MN)$으로는 시간 초과가 뜬다.
  • $O(M\log N)$으로 해결해야 한다.
• 메모리 제약도 있다.
  • 이분탐색을 구현할 때 배열을 재사용하지 않고 매번 새로 만들 경우, 메모리 초과가 된다.

이진 탐색

정렬된 N개의 데이터로 이루어진 배열에서 특정 수 X를 찾아낼 때 사용하는 알고리즘이다.
배열을 중간 값 M을 기준으로 절반으로 쪼갠 후, X가 M보다 작으면 앞쪽 배열에서, M보다 크면 뒤쪽 배열에서 탐색한다. M을 찾을 때까지 계속 반복한다.

정답 코드 및 설명

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int b[] = new int[M];
        for (int i = 0; i < M; i++) {
            b[i] = Integer.parseInt(st.nextToken());
            if (isIn(b[i], a, 0, N))
                bw.write("1\n");
            else
                bw.write("0\n");
        }
        bw.close();

    }

    static boolean isIn(int b, int a[], int min, int count) {
        if (count == 0)
            return false;
        if (count == 1)
            return b == a[min];
        return b > a[min + (count - 1) / 2] ? isIn(b, a, min + (count + 1) / 2, count / 2)
                : isIn(b, a, min, (count + 1) / 2);
    }
}
    

• 이분탐색을 하지 않고 일일히 탐색할 경우 시간 복잡도 : $O(MN)$
• 정렬을 하고 이분탐색을 사용할 경우 시간 복잡도 : $O(M\log N + N\log N)$
  • 정렬의 시간 복잡도 $O(N\log N)$
  • 탐색의 시간 복잡도 $O(M\log N)$
• 이분탐색 과정에서 배열을 계속 새로 만들 경우 공간 복잡도 : $O(MN\log N)$ - 128MB 초과!
  • 재귀 한번할 때 마다 int 변수 N개의 공간이 필요
  • 이분탐색 한 번 당 $O(N\log N)$