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

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

프로그래머스

 

- 난이도: 레벨3

- 분류 알고리즘: 이분탐색(binary search)

 

- 솔루션

class Solution {
	public long solution(int n, int[] times) {

            // 최소 시간은 1분
            long min = 1;
            long max = 0;

            for (int time : times) {
                max = Math.max(max, (long) time);
            }

            // 최대 시간은 가장 느린 심사관이 1명, 하나의 심사대에서 심사할 때
            max = max * n;

            long answer = max;
            while (max >= min) {
                long mid = (min + max) / 2;
                long sum = 0;

                for (int time : times) {
                    sum += mid / time;
                    if (sum >= n) {
                        break;
                    }
                }

                if (sum >= n) {
                    answer = mid;
                    max = mid - 1;
                } else {
                    min = mid + 1;
                }
            }

            return answer;
    }
}

 

 

- 풀이

이 문제에서 구해야 하는 값은 걸리는 시간의 최소값이다. 이진탐색이라는 키워드를 떠올리지 않고 문제를 봤을 때는 , 각 심사대에서 대기하는 인원들이 심사를 끝내고 마칠 때마다 시간을 더하고, 남는 자리를 찾아가서 또 시간을 더하는 방식을 어떻게 구현할 지에 대해 고민했다. 하지만 input인 n의 최대값이 10억이기 때문에 위와 같은 방식으로는 구현이 불가능하다. 

따라서 다른 접근이 필요한데, 시간의 최소값을 구하는 것이기 때문에 이 검색 시간을 임의로 정해 놓고 이진탐색으로 줄여가면서 검색 인원수를 계산하는 것이다. 

 

즉, 총 검색 시간의 최소값과 최대값을 정해놓고 중간값을 계산하여 해당 시간 내에 각 검색대의 검색 인원 수를 선형적으로 계산해서 n 값과 비교하는 방식이다. 검색대의 최대 개수는 10만개이므로, 시간 복잡도는 조건에 만족할 것이다.

 

중간값에 해당하는 시간에 각 검색대에서 처리할 수 있는 인원 수를 모두 더해 n과 비교해서 같거나 크다면, 해당 시간에서는 n명의 인원을 처리할 수 있으므로, 더 작은 시간으로 처리가 가능한지 구하기 위해 시간의 최대값을 중간값보다 작게(이진 탐색)하여 다시 구한다. 만약 n보다 작다면, 주어진 시간 내에  처리가 불가능한 것이므로, 시간의 최소값을 중간값보다 크게(이진 탐색)하여 다시 구한다.   

 

1. min , max 구하기

-  min값은 1분, max 값은 심사대에서 걸리는 심사 시간의 최대값 * 대기 인원 수이다.(가장 느린 심사대 1개에서 모든 대기인원을 처리하는 경우이므로)

 

2.  각 심사대에서 mid 타임 동안 처리할 수 있는 최대 인원 수 구하기

	  for (int time : times) {
                sum += mid / time;
                if (sum >= n) {
                    break;
                }
            }

- 위 코드에서 mid / time의 의미는, time이 각 심사대의 처리 시간이고 mid가 주어진 시간이므로, 주어진 시간 내에 처리할수 있는 인원 수를 의미한다. 이 로직에서 문제에서 주어진 조건인 '남는 심사대가 있으면 찾아가고, 기다렸다가 찾아가도 됨' 을 내포한다. 왜냐하면 mid / time이라는 수식 자체가 그 심사대에서 처리할 수 있는 최대 인원 수를 의미하기 때문이다.

때문에 모든 심사대를 돌면서 처리할 수 있는 인원 수를 모두 더한 sum을 구하면 된다. 근데 만약 sum이 주어진 대기 인원 수인 n보다 크거나 같다면, 이미 해당 mid 시간으로 주어진 인원 수 n을 처리할 수 있다는 뜻이기 때문에 최적화를 위해 break 문들 추가해줬다.

 

3. sum과 n을 비교하여 max, min값 조정

- sum이 n과 같거나 크다면, 주어진 mid 시간이 충분히 커서 모든 심사대가 대기 인원 수를 충분히 커버할 수 있다는 뜻이므로, mid 값이 더 작을 때도 만족할 수 있는지 확인하기 위해 mid를 줄여야한다. 즉, 다시 while 루프를 돌 때는 max가 현재 mid 보다 1작은 값이어야 한다. 이 때 answer를 계속 업데이트 해준다. 

 

- sum이 n보다 작다면, 주어진 mid 시간으로 모든 심사대가 대기 인원 수를 커버할 수 없다는 뜻이므로, mid가 더 클 때를 탐색해봐야 하기 때문에 mid를 늘려야 한다. 즉, 다시 while 루프를 돌 때는 min이 현재 min보다 1이 더 큰 값이어야 한다. 

 

- 시간 복잡도 

분 단위의 시간을 이진탐색으로 줄여나가면서, 각 루프마다 주어진 times에 대한 for 루프를 돌기 때문에, 최대 시간: n, times: m이라고 할 때  -> O(m*(logn))

최대 시간이 이론적으로 10억 * 10억(10의 18제곱)이 가능한데, log(10의 18제곱, 밑2)를 밑변환 공식을 이용해 계산해보면 약 60이 나온다. 즉 최악의 경우 m이 10만일때 약 600만번 탐색해야 하므로 주어진 input의 크기에 비해 매우 효율적인 탐색 방법임을 알 수 있다.