문제

1920번: 수 찾기

접근

• 특정 수들을 입력 받아 먼저 배열에 저장해둔다.
• 찾고자 하는 수들을 입력받아 저장해 둔 배열에 있는지를 검사한다.
• 찾고자 하는 수가 있으면 1, 없으면 0으로 출력한다.
• 다양한 풀이 법이 있겠지만, 해당 문제에선 이분 탐색으로 푸는게 맞다. (-2^31 ~ 2^31 범위)

내 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Test {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] array = new int[n];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(array);

        int m = Integer.parseInt(br.readLine());
        int[] result = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            int temp = binarySearch(array, num, 0, n-1);
            result[i] = temp != -1 ? 1 : 0;
        }

        for (int i=0; i<m; i++) {
            System.out.println(result[i]);
        }
    }

    public static int binarySearch(int[] array, int target, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (start+end)/2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            return binarySearch(array, target, start, mid-1);
        } else {
            return binarySearch(array, target, mid+1, end);
        }
    }
}

• 이분 탐색을 하는 방법을 안다면 쉽게 풀 수 있는 문제이다.
• 찾고자 하는 값이 없다면 -1을 반환하도록 binarySearch()를 구현했는데, 이를 기반으로 조건문을 걸어 출력 시 0 또는 1로 출력한다.