[이분탐색] 입국심사 - Java코드 ★★★

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

 

문제

 

 

이해

몇 분이 가장 최적의 시간인지를 찾으면 된다.

시간을 탐색할 범위는 1 ~ N x times[LastIndex] 이다.

이 범위 안에서 이분탐색을 통해,

해당시간에 n명을 만족하는 경우를 찾아 반환해주면 된다.

 

주의

문제에서 input의 범위는 n은 총 10억명까지, 대기시간은 총 10억 분까지도 들어올수있다.

이분탐색의 맨 우측 끝값이 최악의 경우 10억명 x 10억분 값으로 지정해야하기때문에

long 자료형으로 작성되어야한다.

 

개념

이분탐색 기본 구현 코드

이분탐색의 핵심은 중간지점을 기준으로 비교하면서 새로운 탐색범위를 설정하는것

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] >= target)
        	start = mid +1;
        else  (arr[mid] > target)
            end = mid - 1;
    }
    return mid;
}

탐색범위가 교차되는 순간의 mid값이 구하고자하는 값이 된다.

Left 부분에 ==을 넣어주면,  정답의 경우도 +1로 범위를 위로 추가적으로 더 탐색하기 때문에 최댓값을 찾게되고

Right부분에 ==을 넣어주면, 정답의 경우도 -1로 범위를 아래로 줄이기 때문에 최솟값을 찾게된다.

 

풀이

Overflow에 주의하자.

import java.util.Arrays;
class Solution {
    public static long solution(int n, int[] times) {
        Arrays.sort(times); // 오름차순 정렬
        long r = (long) times[times.length-1] * n; // overflow 주의, 최대 10억명 x 10억분 => long형으로 받아야함
        long l = 1; //  0이라도 상관은 없지만.. 문제에서 1명이상 심사시간 1분이상인 심사관에게 받음
        long mid=0;
        long person=0,result=0;
        while(l<=r){
            mid = (l+r)/2; // 기준 초
            person = 0; // 입국심사 수 count
            for (int time : times)
                person += mid/time;
            if(person>=n){
                r=mid-1;
                result = mid;
            }
            else
                l=mid+1;
        }
        return result;
    }
}

최솟값을 찾아야하므로 right 부분에서 =을 포함시켜 범위를 최대로 줄여가면서

어긋나는 순간에 마지막 만족하던 결과를 반환한다.