[JAVA]백준 알고리즘 10815번 : 숫자 카드

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

10815번: 숫자 카드

문제

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

 

풀이

처음에는 반복문을 이중으로 써서 풀었는데, 시간 초과가 발생했다.

구글링을 해보니 이분 탐색을 이용하면 된다고 해서, 이분 탐색의 개념을 보고 아래 코드를 작성했다.

checking 함수 부분이 이분탐색을 한 부분이다.

 

코드

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

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

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

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            int check = Integer.parseInt(st.nextToken());
            boolean checkTF = checking(card, check);

            if(checkTF) sb.append(1).append(" ");
            else sb.append(0).append(" ");
        }

        System.out.println(sb);
    }
    public static boolean checking(int[] card, int check) {
        int left = 0;
        int right = N - 1;
        while(left <= right) {
            int middle = (left + right) / 2;
            if(check > card[middle]) left = middle + 1;
            else if(check < card[middle]) right = middle - 1;
            else return true;
        }
        return false;
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!