프로그래머스 입국심사

알고리즘 입국심사

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

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

 

이분탐색 시간복잡도

O(logn)

 

주어진 n명의 사람이 주어진 times 배열의 시간을 활용하여 최단시간내에 입국심사를 받으면 되는 문제다.

해당 문제는 이분탐색 카테고리에 되어있다.

사실 이 카테고리 못봤으면 이분탐색으로 생각도 못했을거같다. 많이 풀어봐야겠다.

 

이분탐색의 기준은 시간기준으로 0 ~ times[가장큰값] * n 을 기준으로 탐색을 진행하게 된다.

 

해당문제의 포인트는 주어진 n 을 기준으로 한명씩 심사를 받게 하는것이 아닌 최대의 시간을 가지고 그 시간내에 

n명의 인원이 심사를 완료할수 있는가를 생각해보면 된다.

 

코드

public static long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0; //최단시간을 저장할 변수
        long left = 0; //최저시간
        long right = (long) n*times[times.length-1]; //n명의 고객이 최대의 시간을 거쳐 심사를 받을 수 있는 시간
        long pivot; //중간값을 저장할 변수
        while (left <= right) { //갱신되는 최저시간(left)이 최대시간(right)과 같아지거나 커지면 반복 종료
            pivot = (left + right) / 2; //최저시간과 최대시간의 중간값을 저장한다.
            long sum = 0; //고객의 수를 저장할 변수
            for (long item : times) { //주어진 times 배열을 모두 반복한다
                sum += pivot / item;  //times시간을 현재 pivot(시간)으로 나누어 최대 심사를 받을 수 있는 인원을 구한다.
            }
            if (sum < n) { //심사를 받은 사람이 주어진 n보다 작을경우(시간이 모자란것)
                left = pivot + 1; //left(최저시간)를 갱신하여 다시 반복한다.
            } else { //심사를 받은 사람이 주어진 n보다 크거나 같다(시간이 남을수도 있음)
                right = pivot - 1; //시간이 남을 수 있기때문에 right를 갱신하여 다시 반복
                answer = pivot; //pivot(현재 구한 시간)을 저장
            }
        }
        return answer;
    }