[알고리즘/백준] 1920 수 찾기(자바, 이진탐색, BinarySearch)

문제

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

풀이 코드

• 첫번째 풀이 시도에 List의 contains() 메서드를 사용하여 수의 포함 여부를 계산하여 풀이하였지만 시간 초과로 실패하여 이진 탐색을 사용하여 풀이
• Arrays.binarySearch() 메서드를 사용하여 이진 탐색

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nArr[i] = Integer.parseInt(st.nextToken());
        }

        //이진 탐색은 정렬이 되어있어야 히기때문에 오름차순 정렬
        Arrays.sort(nArr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());

            /*
            Arrays.binarySearch 메서드는 값을 찾으면 그 값의 위치를 반환하고,
            값을 찾지 못하면 만약 그 값이 있었다면 정렬 순서상 있어야되는 위치에 -1을 곱하고 1을 뺀 값을 반환한다.
            */
            if (Arrays.binarySearch(nArr, num) >= 0) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }

        System.out.println(sb);
    }
}