백준 10815 - 숫자 카드 (자바 - 이분 탐색)

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

10815번: 숫자 카드

 

* 문제 요약

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

 

* 입력

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

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

 

* 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

* 예시

 

* 해결 과정

가지고 있는 숫자들을 오름차순으로 정렬해 배열에 저장해준 다음, 가지고 있는지 없는지 확인하기 위한 숫자들이 입력되었을 때 가지고 있는 숫자들이 저장된 배열에 대해 이분 탐색을 수행해서 숫자를 찾은 경우 1, 찾지 못한 경우 0 을 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] cardArray = new int[n];
        for (int i = 0; i < n; i++) {
            cardArray[i] = Integer.parseInt(input[i]);
        }

        int m = Integer.parseInt(br.readLine());
        int[] mArray = new int[m];
        input = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            mArray[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(cardArray);

        for (int i = 0; i < mArray.length; i++) {
            int number = mArray[i];

            int start = 0;
            int end = n;
            while (start + 1 < end) {
                int mid = (start + end) / 2;

                if (cardArray[mid] > number) {
                    end = mid;
                } else {
                    start = mid;
                }
            }

            if (cardArray[start] == number) {
                bw.write(1 + " ");
            } else {
                bw.write(0 + " ");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

크기 별로 정렬된 데이터 셋 안에서 특정값을 기준으로 큰지 작은지에 따라 탐색범위를 최소화 해서 찾고자 하는 숫자가 있는지 없는지 확인하는데 걸리는 시간을 최소화 하였으므로 이분 탐색문제이다.