백준|1920번|수 찾기

문제설명
N개의 정수를 입력받고 그 중에 찾는 수가 있으면 1 없으면 0을 출력하는 프로그램입니다.

작동 순서
1. 입력받을 정수의 개수 N을 입력받습니다.
2. N개의 정수를 입력받고 배열에 저장합니다.
3. 찾을 수의 개수 M을 입력받습니다.
4. M개의 찾을 수를 입력받습니다.
5. 이진탐색을 활용할 수 있도록 입력받은 정수가 저장되어 있는 배열을 정렬합니다.
6. 이진탐색을 활용하여 각각의 정수가 입력받은 정수들 중에 있는지 확인하고 결과에 따라 1 또는 0을 출력합니다.

소스코드

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

public class 백준_1920번_수찾기 {
    static boolean binarySearch(int[] arr, int findNum, int start, int last){
        int pivot=(start+last)/2;
        if(start>last)
            return false;
        if (arr[pivot]>findNum)
            return binarySearch(arr, findNum, start, pivot-1);
        else if(arr[pivot]<findNum)
            return binarySearch(arr, findNum, pivot+1, last);
        else{
            return true;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine());
        int M=Integer.parseInt(br.readLine());
        StringTokenizer st2=new StringTokenizer(br.readLine());

        int[] arr = new int[N];

        for(int i=0;i<N;i++)
            arr[i]=Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        for(int i=0;i<M;i++)
            System.out.println((binarySearch(arr, Integer.parseInt(st2.nextToken()), 0, N-1)) ? 1: 0);
    }
}

후기
굉장히 간단하게 그냥 입력받은 수가 배열 안에 있는지 확인하면 됩니다. 하지만 배열의 길이가 긴 케이스도 있기 때문에 탐색에 O(N)이 걸리는 방식을 쓰면 시간초과가 날 수 있어서 이진탐색을 활용했습니다.