[Baekjoon Online Judge] 1920번: 수 찾기

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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baekjoon1920 {

    static int[] array;

    private static int binarySearch(int start, int end, int check) {

        int mid = (start + end) / 2;

        if (mid >= end) return 0;

        if (array[mid] == check) return 1;
        else if (array[mid] < check)
            return binarySearch(mid + 1, end, check);
        else
            return binarySearch(start, mid, check);

    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        array = new int[n];

        String[] input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            array[i] = Integer.parseInt(input[i]);
        Arrays.sort(array);

        int m = Integer.parseInt(bufferedReader.readLine());

        input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            int check = Integer.parseInt(input[i]);
            System.out.println(binarySearch(0, n, check));
        }

        bufferedReader.close();
    }
}

 

밑의 코드는 Arrays 클래스에 binarySearch 메소드를 활용한 방식이다.

 

public class Baekjoon1920 {

    static int[] array;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        array = new int[n];

        String[] input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            array[i] = Integer.parseInt(input[i]);
        Arrays.sort(array);

        int m = Integer.parseInt(bufferedReader.readLine());

        input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            int check = Integer.parseInt(input[i]);
            int index = Arrays.binarySearch(array, check);

            if(index < 0) System.out.println("0");
            else System.out.println("1");
        }

        bufferedReader.close();
    }
}