[백준] 1920번 : 수 찾기 - JAVA [자바]

백준 1654번 랜선 자르기 문제를 다시 풀려니까 기억이 안나서 찾아보다가
이 문제까지 들어오게 되었다.

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

1920번: 수 찾기

 

이 문제를 통해서 이분 탐색에 대한 개념부터 다시 잡아가려 한다.
아래 내용은 https://st-lab.tistory.com/261 이 블로그의 해설을 보며 정리한 내용이다.

먼저 이분 탐색이란 무엇인가.

이분 탐색은 이진 탐색이라고도 불린다.
가장 쉬운 예시로는 우리가 흔히 하는 업-다운 게임을 떠올리면 쉽겠다.

다만 이 문제에서의 포인트는 '수가 존재하는지' 만 알아내면 되니, 중복 원소에 대한 고려는 필요치 않다.

따라서 이분 탐색을 하기 위해서는 배열이 반드시 크기 순서대로 정렬되어 있어야한다.

이 정렬 알고리즘에 대해서 자료구조와 함께 다룰 필요가 있다고 느껴진다.

이분 탐색의 기본 매커니즘은 아래와 같다.

1. 탐색 범위 내의 배열의 중간 '인덱스' 를 구한다. (중간 크기 즉, 평균값이 아니다.)
2. 중간 인덱스의 값과 key 값(찾고자 하는 수)을 비교한다.
3. key값이 중간 값(중간 인덱스의 값) 보다 작다면 왼쪽 부분을, 보다 크다면 오른쪽 부분을 탐색하고,
    같다면 해당 인덱스를 반환하고 종료한다.

위 3가이 과정을 반복하면 결과적으로 두 가지 경우가 나온다.
1. key 값과 같은 중간 인덱스의 값이 존재하여 해당 인덱스를 찾은 경우
2. key 값과 일치하는 값이 존재하지 않는 경우

탐색 범위의 왼쪽 끝과 오른쪽 끝이 같은 경우까지 탐색을 했는데,
그 값이 key 값과 일치하지 않을 경우, 해당 배열에는 key 값이 존재하지 않는 것.

여기서는 값의 존재 유무만을 판별하기에 없다면 음수를 반환한다.

이러한 이진 트리 형태의 경우 시간 복잡도는 거의 O(logN)을 갖는다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arrN = new int[N];
        for(int i = 0 ; i < N; i++) arrN[i] = sc.nextInt();

        Arrays.sort(arrN);

        int M = sc.nextInt();

        for(int i = 0; i < M; i++){
            if(binarySearch(arrN, sc.nextInt()) >= 0) System.out.println(1);
            else System.out.println(0);
        }
    }

    // 정렬된 arr 배열과 찾고자 하는 key 값이 들어온다.
    public static int binarySearch(int[] arr, int key) {
        int lo  = 0;
        int hi = arr.length - 1;


        // 최조에 lo는 0이고 hi는 arr.length-1 이다.
        // mid 는 lo + hi / 2 이다.

        while(lo <= hi){

            int mid = (lo + hi)/2;

            // 그럼 여기서 key 값이 arr[mid] 보다 크다면 Up인거고
            // lo는 mid가 되고 기존 mid는 새로 구한다.
            if(key < arr[mid]){
                hi = mid - 1;
            }
            // 그럼 여기서 key 값이 arr[mid] 보다 작다면 Down인거고
            // hi는 mid -1이 되고 기존 mid는 새로 구한다.
            else if (key > arr[mid]) {
                lo = mid + 1;
            }
            // 그럼 여기서 key 값이 arr[mid] 와 같다면 mid를 return하고
            else return mid;
        }

        // 그럼 여기서 io와 hi가 같아졌는데도 key 값이 없다면 -1을 return한다.
        return -1;
    }
}