[문제풀이] B1920 수찾기

수찾기

---

  🪅 중첩 for문을 도는 것 대신, 다른 시간복잡도가 낮은 탐색과정을 알고있는가
  🪅 이진탐색을 위한 조건을 알고 있는가 => 정렬되어 있어야한다.
  🪅 이진탐색을 구현할 수 있는가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    public static int binarySearch(int target) {
        int low = 0;
        int high = arr.length - 1;
        while(low <= high) {
            int mid = (low + high)/2;
            if(arr[mid] == target) {
                return 1;
            } else if(arr[mid] < target) {
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return 0;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(token.nextToken());
        }
        Arrays.sort(arr);
        int M = Integer.parseInt(br.readLine());
        token = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < M; i++) {
            int cur = Integer.parseInt(token.nextToken());
            int res = binarySearch(cur);
            System.out.println(res);
        }
    }
}

💡 문제 접근 과정
N과 M은 각각 최대 100_000까지 나올 수 있다.
즉, 최대 100_000개(M)를 하나하나 100_000개(N) 중에서 있는지 확인해야하니까 중첩for문을 돌게 되고,
1억번의 연산을 확연히 뛰어넘는다.
따라서 시간초과가 날 것이고, 시간복잡도가 O(logN)인 이진탐색을 이용해야겠다 싶었다.
이진탐색은 정렬된 상태여야 하니 Arrays.sort()로 정렬해주고, 연습삼아 이진탐색을 구현하였다.

📌 Arrays.binarySearch(arr, 탐색값)을 이용하면 쉽게 구현가능하다