[알고리즘] 1920번

오늘 풀어볼 문제는 백준 1920번 문제 "수 찾기" 이다.

이 문제는 실버4 문제이고 이진 탐색 문제이다.

문제

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

📌첫 번째 도전📌
위 문제는 이진 탐색으로 원하는 수를 찾는 문제이다. 그래서 이진 탐색 코드를 find라는 메서드로 만들어서 해결했다.

public class Main {
    static int[] arr;
    static int N;
    static int M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        arr = new int[N];

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

        Arrays.sort(arr);

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            int target = Integer.parseInt(st.nextToken());
            find(target);
        }
    }
    private static void find(int num) {
        int start = 0;
        int end = arr.length - 1;
        boolean check = false;
        while(start <= end) {
            int mid = (start + end)/2;
            int midV = arr[mid];
            if(num < midV) {
                end = mid - 1;
            }
            else if(num > midV) {
                start = mid + 1;
            }
            else {
                check = true;
                break;
            }
        }
        if(check) {
            System.out.println(1);
        }
        else {
            System.out.println(0);
        }
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1920