[프로그래머스]JAVA - Level3. 입국심사

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

프로그래머스

풀이

알고리즘 2단계를 간간히 풀다가 3단계를 처음으로 풀어봤습니다.

심사하는데 걸리는 시간이 다른 각 각의 심사관들이 N명을 검사하는데 걸리는 최소 시간을 구하는 문제입니다.
처음에는 1초씩 더 해가면서 풀었더니 시간 초과가 발생해서 이분 탐색을 이용해서 풀었습니다.

1. 심사하는데 걸리는 시간의 최소값(min)과 최대값(max)을 구함
2. 최소값과 최대값의 중간값(mid) [이분 탐색 시간] 을 구함
3. 이분 탐색 시간동안에 심사관들이 몇 명을 처리할 수 있는지(people)를 구함

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times); // 정렬
        
        long min = 1; // 최소값
        long max = (long) times[times.length-1] * n; // 최대값
        
        while (min <= max) {
            long mid = (min + max) / 2; // 중간값
            long person = 0;
            
            for (int i=0; i<times.length; i++) {
                person += mid / (long) times[i]; // 주어진 시간동안 심사할 수 있는 사람 수
            }
            
            if (person >= n) { // 심사를 받아야할 인원보다 적을 경우 (시간이 부족함)
                max = mid - 1;
                answer = mid;
            } else if (person < n) { // 심사를 받아야할 인원보다 클 경우 (시간이 남음)
                min = mid + 1;
            }
        }
        
        return answer;
    }
}