[BinarySearch] 백준 1920

처음에는 선형탐색을 생각했지만 정렬을 한 번만 해 둔다면 이진탐색이 성능 상 더 좋은 알고리즘이 될 것으로 판단했다.

 

[자바 소스코드]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] inputs;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        inputs = new int[len];

        for(int i=0; i<len; i++){
            int tmp = sc.nextInt();
            inputs[i] = tmp;
        }

        Arrays.sort(inputs); // 오름차순 정렬, 기본적으로 퀵 소트 기반임

        int toBeFoundCount = sc.nextInt();
        for(int i=0; i<toBeFoundCount; i++){
            int target = sc.nextInt();
            solve(len, target);
        }
    }

    private static void solve(int len, int target) {
        int start = 0;
        int end = len - 1;
        int mid;

        while(end - start >= 0){
            mid = (start + end) / 2;

            if(inputs[mid] == target){
                System.out.println("1");
                return;
            }
            else if(inputs[mid] > target){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }

        System.out.println("0");
    }
}

[시간복잡도 분석]

1. 찾을 대상의 범위를 1/2배 씩 줄여가며 탐색하기 때문에 (밑이 2인) O(logN) 성능을 보인다.

2. 이진 탐색을 M번(찾을 대상의 개수) 호출하기 때문에 O(MlogN) 이다.

3. 한 번의 퀵 소트가 필요하므로 최악의 경우 MlogN + N^2, 평균적으로 MlogN + NlogN 시간복잡도를 갖는다.

4. 퀵 소트의 경우 최악의 경우가 발생할 가능성이 매우 적으므로 찾을 값의 개수인 M값에 따라 시간복잡도가 결정된다. 찾을 값의 개수가 배열 길이보다 작거나 같다는 가정 하에, 이 문제는 평균적으로 NlogN의 성능을 갖는다.

 

[새로 알게된 점]

Arrays.sort는 기본적으로 퀵 소트 알고리즘 기반으로 정렬한다는 것을 알게 되었다.

 

[진행과정 중 실수]

1. 문제

초기에 입력을 받은 배열 inputs에 길이를 최대 입력인 100,000으로 설정해 두고 binary search를 돌렸으나 0만 출력되는 문제가 발생했다.

 

2. 원인 파악

입력 길이보다 더 큰 배열 공간을 잡고 Arrays.sort(inputs)를 호출시키면 inputs의 앞쪽에는 0만으로 가득찰 것인데, 이 상태로 입력 길이 만큼 이진 탐색을 돌리면 [0,0,0,......,0,0] 을 대상으로 이진 탐색을 돌리는 것과 같은 효과일 것이다. 그래서 0만 출력이 되었던 것이었다.

 

3. 해결

입력 크기를 입력 받은 후, 해당 크기만큼 배열의 길이를 설정해 주었다.

 

[TODO]

재귀 기반의 이진탐색