백준 10815 자바 - 숫자 카드

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

10815번: 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

코드

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

public class Baekjoon10815 {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
        int m = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st1.nextToken());
        }
        Arrays.sort(arr);

        for (int i = 0; i < m; i++) {
            int result = binarySearch(Integer.parseInt(st2.nextToken()), arr);
            if (result != -1) {
                sb.append("1 ");
            }
            else {
                sb.append("0 ");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }

    private static int binarySearch(int target, int[] array) {
        int left = 0, right = array.length - 1, mid;
        while(left <= right) {
            mid = (left + right) / 2;
            if (array[mid] < target) {
                left = mid + 1;
            }
            else if (array[mid] > target) {
                right = mid - 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

}

풀이

 그냥 컬렉션으로 contains하면 시간 오류가 난다. 이분 탐색을 위한 메소드 하나를 구현해 마지막줄의 입력받은 값들을 하나씩 돌리면 된다.