백준 1920 수 찾기 [JAVA]

문제 해석

• 문제는 기준이 되는 배열(=N-Array)기준으로 새로 입력받는 배열(M-Array)의 각각의 요소가 기준 배열(N-Array)에 있는 요소인지 확인해서 있을 경우 1, 없을 경우 0 을 출력하면 되는 문제이다.
• 단순히 반복문안에 반복문을 넣어서 탐색하게 되면 시간제한에 걸릴 것이다. (직접해봤는데 당연하게도 시간초과가 나왔다.)
• 그렇다면, 시간을 어떻게 해서 아낄 수 있는지 생각을 해봐야하는데 자연스럽게 '탐색법'을 생각하게 될 것이다. 탐색시간을 최소화하는 법!
• 여기서 '이진탐색법'을 생각했다. 배열을 정렬한 후 기준 요소를 잡고 크고 작은지를 판단하여 기준에 맞춰 1/2씩 쪼개 탐색하면 되니까 그냥 반복문을 2번쓰는 (O(N^2))보단 빠를 것이다!
• 그렇다면 이진탐색은 무엇일까? (말로 설명하기 어려워서 그림으로 설명하겠다...ㅎㅎ)
  
• 위와 같은 방식으로 탐색하는 것을 이진탐색이라 한다.

코드

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

public class Main {

    static int[] NArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        NArr = new int[N];

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

        Arrays.sort(NArr); // 배열 정렬

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            if(sortSearch(Integer.parseInt(st.nextToken())) != 0){
                sb.append("1").append("\n");
            }else{
                sb.append("0").append("\n");
            }
        }
        br.close();

        System.out.println(sb);
    }

    static int sortSearch(int num){
        int start = 0;
        int end = NArr.length-1;
        int middle;

        while(start <= end){

            middle = (start+end)/2;

            if(NArr[middle] > num){
                end = middle-1;

            }else if(NArr[middle] < num){
                start = middle+1;

            }else if(NArr[middle] == num){
                return NArr[middle];
            }
        }
        return 0;
    }
}

결과

느낀 점

이진탐색 방법을 사용해서 풀었는데 전에도 이런 문제는 많이 접해서 그런지 큰 어려움 없이 풀 수 있었다.