숫자카드


백준 [10815] 숫자 카드

문제보기
Alt text

풀이

Set을 활용하여 포함 여부를 판별해도되지만, 이분 탐색으로 풀어보았음

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] sangenCards = new int[N];
        for (int i = 0; i < N; i++) {
            sangenCards[i] = sc.nextInt();
        }

        int M = sc.nextInt();
        int[] checkCards = new int[M];
        for (int i = 0; i < M; i++) {
            checkCards[i] = sc.nextInt();
        }

        Arrays.sort(sangenCards);

        for (int i = 0; i < checkCards.length; i++) {
            int target = checkCards[i];

            int mid = sangenCards.length / 2;
            int left = 0;
            int right = sangenCards.length - 1;

            boolean hasNum = false;
            while (left <= right) {

                if (sangenCards[mid] == target) {
                    hasNum = true;
                    break;
                }

                if (sangenCards[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

                mid = left + ((right - left) / 2);
            }

            System.out.print((hasNum ? 1 : 0) + " ");
        }
    }
}