[Baekjoon Online Judge] 10815번: 숫자 카드

10815번: 숫자 카드

요구사항

 - 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구한다.

입력

 - 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.

 - 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

 - 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

 - 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

기본적인 이분탐색 문제이다. 두 가지 방식을 활용하여 풀이하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baekjoon10815 {

    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.print(binarySearch(0, n, check) + " ");
        }

        bufferedReader.close();
    }
}

 

public class Baekjoon10815 {

    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.print("0 ");
            else System.out.print("1 ");
        }

        bufferedReader.close();
    }
}