[Programmers Lv.3][입국 심사][java]

문제 링크

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

프로그래머스

---

알고리즘 

ex. 30분일 때

1번 심사관은 30 / 7 = 4 → 최대 4명 심사할 수 있음

2번 심사관은 30 / 10 = 3 → 최대 3명 심사할 수 있음

총 7명 심사할 수 있고 n보다 크므로, 현재까지 mid 가 최솟값임 → right 줄이고 answer에 mid 값 임시 저장

각 심사관이 최대 몇명을 심사할 수 있고 그 수가 n보다 작은 경우, 크거나 같은 경우로 따져서 탐색하자

 

전체 코드

import java.util.*;

public class Solution72412 {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 1; // 최선의 경우
        long right = (long) times[times.length - 1] * n;  // 최악의 경우

        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0;
            for(int t : times)
                sum += mid / t;  // 심사관마다 중간 시간을 기준으로 심사할 수 있는 사람 수의 합

            if (sum < n) // 심사하는 사람 수가 적을 때 시간을 늘림 
                left = mid + 1;
            else {  // 심사하는 사람의 수가 더 많거나 같을 때 시간을 줄임
                right = mid - 1;
                answer = mid; // mid 는 right 가 줄어들 경우에 최솟값이므로 answer에 저장 
            }
        }
        return answer;
    }
}

 

코드 리팩토링

left = times[0] 여도 됨