[ BOJ ][JAVA][1920] 수 찾기

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

1920번: 수 찾기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	98267	31265	20394	30.700%

문제

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을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

코드

/*
    수찾기
    이분탐색

    HashSet을 이용하면 훨씬 빠르고 간단하게 찾을 수 있다.
    이분탐색 연습용!
*/
import java.io.*;
import java.util.*;

public class p1920 {
    static int n, m;
    static int[] a, b;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

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

        Arrays.sort(a);
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < m; i++) {
            if(solution(a, 0, n - 1, b[i])) ans.append(1).append('\n');
            else ans.append(0).append('\n');
        }
        System.out.println(ans);
    }
    static boolean solution(int[] arr, int l, int r, int target) {
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] == target) return true;

            if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }

        }

        return false;
    }
}