[Java] 프로그래머스 입국심사

1. 문제분석

문제를 보고 심사관의 수 만큼 배열을 생성해 사람이 들어갈 수 있는 공간을 만들려고 했다.

하지만 입국심사를 기다리는 사람이 10억명까지 나오고 시간 또한 10억분이 나온다.

한개씩 데이터를 사용하기엔 너무 오랜시간이 걸리기 때문에 이분탐색을 사용한다.

 

이분탐색은 우리가 아는 이진탐색과 동일하다.

1부터 12까지, 우리가 찾고자 하는 데이터가 9라고 생각해보자.

그렇다면 1과 12의 가운데에서 값을 찾아가는 것이다.

가운데 값은 (start + end) / 2로 쉽게 구할 수 있다.

이제 end가 찾고자하는 값보다 큰지, 작은지를 구하면 조건에 맞지 않는 값 절반이 버려진다.

mid가 찾고자하는 값보다 크기 때문에 mid의 뒤에 값은 버려도 상관없다.

또한 mid까지 값을 비교했으니 mid도 버리고 결과적으로 mid + 1이 된다.

이번엔 운이 좋게 mid와 9가 곂쳤다. 이렇게 하면 기존 O(N)에서 O(logN)이 된다.

 

이제 문제를 해결해보자.

2. 구현

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        //이분탐색을 위한 정렬
        Arrays.sort(times);

        //시작은 아무리 빨라도 가장 빠른 시간을 지나침
        long start = times[0];
        //마지막은 제일 늦으면 가장 느린 수 * 사람 수
        long end = (long) times[times.length-1] * n;
        long mid = 0;

        //end 가 start 와 작거나 같다면 이분탐색 종료
        while(start <= end){
            long completePeople = 0;
            //가운데 값 구하기(값을 기준으로 데이터를 찾음)
            mid = (start + end) / 2;
            //시간내 처리할 수 있는 사람들
            for (int time : times) {
                completePeople += mid / time;
            }
            //심사를 받아야할 사람보다 완료된 사람이 적다면?
            if(completePeople < n){
                //왼쪽은 없다. start 를 mid + 1로 바꿔주자.
                start = mid + 1;
            }
            //최솟값이 아니다. -> 완료된 사람이 더 많다.
            else{
                //오른쪽은 없다. end 를 mid - 1로 바꿔주자.
                end = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}​

이번에도 이분탐색을 적용해보자.

최소 걸리는 시간은 제일 빠른 시간, 최대 걸리는 시간은 제일 오래 걸리는 시간 * 사람수가 된다.

또한 end가 start와 곂치게 되는 순간 값이 없거나 이미 찾은 것이니 while문을 통해 반복한다.

 

start와 end를 구했다면 이제 mid를 통해 이분탐색을 해보자.

우리는 입국심사를 마치는 최소시간을 구해야 한다. 먼저 시간을 구하고 그 시간안에 몇명을 처리하는지를 구한다.

그리고 그 수가 매개변수로 주어진 사람수와 같을때까지 구한다.

 

하지만 위의 코드를 보면 answer와 mid가 같은 경우는 존재하지 않는다. 왜일까?

 

    	for (int time : times) {
                completePeople += mid / time;
            }
            //심사를 받아야할 사람보다 완료된 사람이 적다면?
            if(completePeople < n){
                //왼쪽은 없다. start 를 mid + 1로 바꿔주자.
                start = mid + 1;
            }
            //최솟값이 아니다. -> 완료된 사람이 더 많다.
            else{
                //오른쪽은 없다. end 를 mid - 1로 바꿔주자.
                end = mid - 1;
            }
            //같은 경우 반환
            if(completePeople == n){
                return mid;
            }

다음과 같이 completePeople == n인 경우를 반환해보자.

테스트케이스를 대입하면 28이 아닌 29가 나온다. 왜 그렇게 나오는지 한번 해보자.

맨 처음 mid는 (7+60)/2 = 33.5가 되지만 내림으로 33이 된다.

33분 내에는 (33/7) + (33/10) = 7이므로 7명을 처리할 수 있다. 우리는 6명만 처리하면 되므로 mid를 줄여야한다.

계속하면 start = 27, end = 32, mid = 29가 나온다. 이 경우 completePeople 또한 6을 만족한다.

 

하지만 이게 우리가 구하고자하는 값일까? return을 안하고 더 해보자.

일단 mid는 만족했다. 우리는 최솟값을 구해야하니 값을 더 줄여야 한다.

위의 조건대로 한다면 mid = end - 1이 된다. 그러면 start = 27, end = 28, mid = 27이 된다.

(27/7) + (28/10) = 5로 값을 만족하지 못한다. 

결과적으로 더 빠른 시간이 있다면 구하게 되는거고 못구한다면 while문의 조건으로 루프를 나오게 된다.

3. 마무리

이분탐색이 뭐야? 라고 생각했던 나, 가끔은 대학교를 졸업한 사람이 맞나 싶다. 

이분탐색은 2학년 때 배운 지식인데 이걸 몰라서 이분탐색을 구글링했다 ㅋㅋㅋㅋㅋㅋ..

하지만 개념만 안다면 생각보다 쉽게 구할 수 있다.