백준 1920. 수 찾기(JAVA)

○ 문제 요약

N개의 정수의 값이 M개의 정수를 가진 배열에 포함되어 있는지 출력해라.

○ 문제 풀이

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

public class Main {

    static int[] arr;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

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

        arr = new int[N];

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

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

        Arrays.sort(arr);
        int M = Integer.parseInt(br.readLine());

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

        for(int i = 0 ; i < M ; i++){
            if(BinarySearch(Integer.parseInt(st.nextToken()))>=0){
                sb.append(1).append('\n');
            }else{
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);
    }

    public static int BinarySearch(int value){

        int lo = 0;
        int hi = arr.length -1;

        while(lo <= hi){

            int mid = (lo + hi)/2;

            if(value < arr[mid]){
                hi = mid - 1;
            }else if(value > arr[mid]){
                lo = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

처음으로 이분 탐색법을 사용해서 문제를 해결했다. 이분 탐색법에 대한 내용은 추후에 정리해서 올릴 예정이다.

 

이 문제를 풀면서 이분 탐색법의 핵심은 계속 반으로 분할해서 정하는 값을 찾는 것이다. 그래서 BinarySearch 메서드를 보면 찾고 싶은 값을 기준으로 찾고 싶은 배열의 인덱스를 조정해가면서 값을 비교하는 것을 알 수 있다. 

 

예제 입력을 예로 설명해보면

4

1

5

2

3

arr 배열은 위처럼 값이 들어있고 추가적으로 배열은 생성하지 않고 입력받는 대로 사용했다.

이분 탐색법을 할 때, 반드시 배열을 정렬해주어야 한다. 정렬을 깜박하고 출력을 했을 때 전혀 다른 값이 나온다. 그러므로 이 점 유의하도록 하자!

arr 배열에 value 값이 포함되어 있는지 확인하기 위해 arr의 중간 index를 구해주고 그 index의 값이 value의 값과 같은지 비교한다. 만약에 value의 값이 더 작다면 hi = mid - 1을 해서 더 작은 index값과 비교할 수 있도록 해준다. 반대로 value의 값이 더 크다면 lo = mid + 1을 해서 더 큰 index값과 비교할 수 있도록 해준다. 그래서 index 값과 value 값이 같다면 그 index값을 반환해준다. 

 

이 과정을 M만큼 반복 수행하면 원하는 값을 출력할 수 있다. 

 

○ 결과