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

https://programmers.co.kr/learn/courses/30/lessons/43238?language=java 

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

이분탐색을 이용하여 입국 심사에 필요한 가장 짧은 시간을 구하는 문제입니다.

이분탐색에서는  start, end 값을 어떻게 정의할 것인가, 어떤 기준으로 mid 와 start/end 를 바꿔나갈 것인가  가 쟁점입니다.

1. 최소시간 start 는 1분이다
2. 최대시간 end 는 가장 느린 심사관이 모든 고객을 혼자 처리하는 시간이다.
3. mid에 처리할 수 있는 고객의 수는 (mid / time) 을 전부 더해준 값이다.
4. 만약 mid 시간 동안 처리할 수 있는 고객의 수가 n 보다 작다면 start = mid + 1 아니라면 end = mid 로 바꿔준다.
5. 최종적으로 start = end 일때 while loop 를 벗어나며 end 값을 반환한다.

 

주의사항

문제 정의를 보면 입국 심사를 기다리는 사람은 최대 1,000,000,000 (10^9, 10의 9승) 명,

한 심사관이 한 사람을 처리하는데 걸리는 시간은 최대 1,000,000,000 (10^9) 분이다. 

따라서 start, end, maxNum, mid 는 최대 10^9 * 10^9 = 10^18 이다.

자바의 int 타입은 32 bit 로 최대 4,294,967,296 까지 표현가능 하고 따라서 본 문제에서 필요한 변수들을 표현하는데 부족하다.

자바의 long 타입은 64 bit 로 약 10의 19승 까지 표현할 수 있고, 따라서 모든 변수에 long 타입을 이용해야 정확한 답을 구할 수 있다.

(maxNum 을 int 로 설정해서 테스트케이스 9번을 통과하지 못해 30분이상 헤맸음 ㅜㅜ)

 

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        // 최소 시간, 최대 시간
        long start = 1;
        long end = (long) times[times.length - 1] * n;

        while (start < end) {
            // 중간 시간
            long mid = (start + end) / 2;
            // 중간 시간 동안 몇명의 고객을 처리할 수 있는가
            long maxNum = 0;
            for (int i = 0; i < times.length; i++) {
                maxNum += mid / times[i];
                // mid 시간동안 처리할 수 있는 고객이 n 이상이되면 바로 for loop 탈출
                if (maxNum >= n) {
                    break;
                }
            }
            
            // start, end 업데이트
            if (maxNum < n) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        long answer = end;
        return answer;
    }
}