최고의 개발자 (목표)

문제

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

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2³¹보다 크거나 같고 2³¹보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

코드

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 N;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());

        int[] targets = new int[M];
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < M; i++){
            targets[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < M; i++){
            int result = binarySearch(targets[i]);

            sb.append(result == -1 ? 0 : 1);
            sb.append("\n");
        }

        System.out.println(sb.toString());


    }

    static int binarySearch(int target){
        int left = 0;
        int right = N - 1;
        int mid;

        while(left <= right){

            mid = (left + right) / 2;
            
            if(arr[mid] == target){
                return mid; // 탐색 완
            }

            if(arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }

        }
    
        return -1; // 탐색 실패
       
    }
}

이 문제를 푸는 여러 방법이 있겠지만, 이분 탐색을 공부하는 김에 사용해보았다. left, right, mid는 A의 index를 의미하고, left와 right을 이용해 mid의 값을 갱신해나가며 값을 찾는다. A배열의 left부터 right까지 확인하여 target이 있는지 찾으면 된다. 이때, A 배열은 정렬이 되어 있어야 한다. left <= right 일 때까지 돌면서 반복하고, 만약 target 값과 A[mid]의 값이 같다면 target이 A 안에 있다는 의미이기 때문에 mid 값을 리턴한다. 만약 A[mid]가 target 보다 크다면, mid보다 왼쪽에 target이 있다는 의미이기 때문에 right을 `mid - 1`로 변경하여 A[left] ~ A[mid - 1] 까지의 배열만 탐색하도록 한다. 만약 A[mid] 가 target 보다 작다면 target이 mid 보다 오른쪽에 있다는 의미이기 때문에, 그 후에 탐색할 때는 A[mid + 1]부터 A[right]까지만 보면 된다. 따라서 left를 `mid + 1`로 변경하면 된다. 만약 while 문을 통과했는데 리턴하지 못했을 때는 A 배열에 target이 존재하지 않는 것이기 때문에 -1을 리턴한다.