[실전 문제] 숫자박스

1. 문제

숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오. 

---

입력

첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 절댓값 1,000,000 이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

 

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다.  

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 숫자 상자안에 있으면 1, 아니면 0을 개행으로 구분해 출력한다.

예제 입력

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력

1
0
0
1
1
0
0
1

 

 

 

2. 풀이

이 문제는 이진 탐색을 이용하여 풀 수 있다. 단, 정렬된 배열에서 사용할 수 있다는 점을 주의해야한다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int q;
    private static int[] arr;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        
        q = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < q; i++) {
            int value = Integer.parseInt(st.nextToken());
            bw.write(binaySearch(0, n-1, value) + "\n");
        }

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

    private static int binaySearch(int s, int e, int value) {

        if(s > e) return 0;
        if(s == e) {
            if(arr[s] == value) return 1;
            else return 0;
        } else {
            int mid = (s+e)/2;
            if(arr[mid] < value) return binaySearch(mid+1, e, value);
            else if(arr[mid] > value) return binaySearch(s, mid-1, value);
            else return 1;
        }
    }
}