8-1: 숫자박스

숫자박스 (numberbox.cpp)

 

문제

---

숫자박스에는 자연수들이 적혀있는 종이들이 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

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

public class numberbox {

    /**
     *
     * 문제: 숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오.
     *
     *
     * 입력:
     *
     * 첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 1,000,000이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.
     *
     * 셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다.
     *
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     *
     * 예제 출력:
     *
     *
     * @param args
     */

    public static int[] myNums;

    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();

        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);

        int N = Integer.parseInt(br.readLine());
        myNums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i=0; i<N ;i++){
            myNums[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(myNums);

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i=0; i<M; i++){
            int index = binarySearch(Integer.parseInt(st2.nextToken()));
            int result = index >= 0? 1:0;
            System.out.println(result);
        }

    }

    private static int binarySearch(int targetNum) {
        int start = 0;
        int end = myNums.length -1;
//        int mid = myNums.length / 2;
        if (targetNum < myNums[0] || targetNum > myNums[myNums.length-1]) return -1;

        //cmp myNums[mid] and targetNum
        while (start <= end){
//            System.out.println("start : " + start+ ", end: " + end);
            int mid = (start+end) / 2;

            if (myNums[mid] > targetNum){
                //search lower half
                end = mid-1;
            } else if (myNums[mid] < targetNum){
                //search upper half
                start = mid+1;
            } else return mid;
        }
        return -1;
    }


    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) return;

        int pivot = arr[(leftIndex+rightIndex)/2];

        int index = partition(arr, leftIndex, rightIndex, pivot);

        quickSort(arr, leftIndex, index-1);
        quickSort(arr, index, rightIndex);
    }

    private static int partition(int[] arr, int leftIndex, int rightIndex, int pivot) {
        while (leftIndex <= rightIndex){
            while (arr[leftIndex] < pivot){
                leftIndex++;
            }

            while (arr[rightIndex] > pivot){
                rightIndex--;
            }

            if (leftIndex <= rightIndex){
                swap(arr, leftIndex, rightIndex);
                leftIndex++;
                rightIndex--;
            }
        }
        return leftIndex;
    }

    private static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}