[백준] S4 1920번 수 찾기 (Java)

https://www.acmicpc.net/problem/1920

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

N의 최대 범위가 100,000이므로 단순 반복문으로는 이 문제를 풀 수 없습니다. 이진 탐색을 적용하면 O(nlogn)의 시간 복잡도로 해결할 수 있으므로 이진 탐색을 적용합니다. 그리고 이진 탐색은 정렬을 가정하므로 정렬 함수도 사용합니다.

1. 입력받는 N개의 정수 A[1], A[2], ... , A[N]를 1차원 배열에 저장한 다음 저장된 배열을 정렬합니다.

2. M개의 수들이 각각 존재하는지 이진 탐색을 사용해 확인합니다.

👉 풀이

import java.util.Arrays;
import java.util.Scanner;

public class P1920_수찾기_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        Arrays.sort(A);

        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            boolean find = false;
            int target = sc.nextInt();

            // 이진 탐색 시작
            int start = 0;
            int end = A.length - 1;

            while (start <= end) {
                int midIndex = (start + end) / 2;
                int midValue = A[midIndex];

                if (midValue > target) {
                    end = midIndex - 1;
                } else if (midValue < target) {
                    start = midIndex + 1;
                } else {
                    find = true;
                    break;
                }
            }

            if (find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

👉 성능