[알고리즘] 백준 10815 - 숫자 카드

1. 문제

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

2. 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

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

3. 풀이

N 배열을 정렬해주고, 모든 M에 대해 N 배열을 기준으로 이분탐색해준다.

4. 코드

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

public class numCard_10815 {

    static int n,m;

    static int[] n_arr,m_arr;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

        n = Integer.parseInt(bf.readLine());
        n_arr = new int[n];
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        for(int i=0;i<n;i++){
            n_arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(n_arr);

        m = Integer.parseInt(bf.readLine());
        m_arr = new int[m];
        st = new StringTokenizer(bf.readLine()," ");
        for(int i=0;i<m;i++){
            m_arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0;i<m;i++){
            int left = 0;
            int right = n-1;

            int index = 0;
            while(left<=right) {
                int mid = (left+right)/2;

                if(m_arr[i]<=n_arr[mid]){
                    index = mid;
                    right = mid-1;
                }
                else{
                    left = mid+1;
                }

            }

            if(m_arr[i]==n_arr[index])
                answer.append(1+" ");
            else
                answer.append(0+" ");

        }

        System.out.println(answer);

    }
}