링크

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

풀이

import java.util.*;

public class boj_1920 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arrN = new int[N];

        for (int i = 0; i < N; i++){
            arrN[i] = scanner.nextInt();
        }

        Arrays.sort(arrN);

        int M = scanner.nextInt();
        int[] arrM = new int[M];

        for (int i = 0; i < M; i++){
            arrM[i] = scanner.nextInt();

            System.out.println(binary(arrN, arrM[i], 0 , N - 1));
        }



    }

    static int binary(int[] array, int target, int start, int end) {

        while (start <=  end) {
            int mid  = (start +  end) / 2;
            if (array[mid] == target)
                return 1;
            else if (array[mid] > target)
                end = mid -  1;
            else
                start = mid + 1;
        }
        return 0;

    }
}

설명

책과 강의에 있던 문제와 비슷한 문제인 것 같길래 선택해서 풀어본 이진탐색 관련 문제. 문제 그대로 찾는 target 값이 존재하면 return 1을 하고, 존재하지 않으면 0을 return하여 결과를 나타내는 문제였다.