[이분 탐색] 프로그래머스 Level 3 입국심사 Java 풀이

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

프로그래머스

문제 풀이

1. times를 오름차순 정렬한다.
2. 가장 큰 시간(times의 마지막 인덱스)에다가 n을 곱해서 가장 오래 걸리는 경우의 시간을 구한다.
   즉, 모든 사람이 가장 오래 걸리는 시간의 입국심사대를 가는 상황이다.
3. 시작 시간(start)과 가장 오래 걸리는 시간(end)을 반으로 나눈 값을 mid라는 변수에 저장한다.
4. times 배열을 순회하며 mid 변수를 times 배열의 요소로 나누어서 completed라는 변수에 더한다.
   즉, mid 시간 동안에 입국 심사를 받을 수 있는 사람 수를 세는 과정이다.
5. completed라는 변수의 크기가 n보다 작으면, 그 mid 시간동안 n명의 입국심사를 모두 할 수 없음을 의미한다.
6. 따라서 mid의 값을 크게 하기 위해 start를 mid + 1로 설정한다
7. 반대로 completed의 크기가 n보다 크면 그 mid 시간동안 n명의 입국심사를 모두 할 수 있다는 것인데,
   입국심사를 다 하고 시간이 남았을수도 있으므로 end를 mid - 1로 설정한다.
8. start 값이 end 값보다 커지면 멈춘다.

코드

import java.util.*;


class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        
        long start = 0;
        long end = (long)n * times[times.length - 1];
        while(start <= end) {
            long mid = (start + end) / 2;
            long completed = 0;
            for(int i = 0; i < times.length; i++) {
                completed += mid / times[i];
            }
            if (completed < n) {
                start = mid + 1;
            } else {
                end = mid - 1;
                answer = end;
            }   
        }
        
        return answer + 1;
    }
    
}