📝문제

간단하게 수를 찾는 문제. 하지만 무작정 반복문을 사용해서 해결하려고 하면 시간초과가 날 것이다.
어떤 방법이 좋을까 고민하다가 학부 때 배운 이분탐색을 이용하면 되지 않을까? 했다.
근데 막상 이렇게 해결하고나서 다른 분들의 코드를 보니 간단하게 hashset을 사용하는 방법도 있었다.
괜히 정렬하고 재귀로 연산하는 것보다 훨씬 코드가 간결하고 시간도 적게 소요된다.

📌코드

package Baekjoon;

/**
 * 정수의 범위 : -2^31 ~ 2^31 -> int
 * 탐색 알고리즘
 */

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

public class BOJ1920 {

    static int n;
    static int[] arr;

    static void binary(int start, int end, int target){
        if(arr[start] == target || arr[end] == target || arr[(start+end)/2] == target){
            System.out.println(1);
        }
        else if(start + 2 < end) {
            if(target < arr[(start+end)/2]) binary(start, (start+end)/2 - 1, target);
            else binary((start+end)/2 + 1, end, target);
        }
        else System.out.println(0);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            binary(0, n-1, Integer.parseInt(st.nextToken()));
        }
    }
}