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

[blossun]

• 문제

아이디어

• 입력값 최대범위가 엄청 크고 최소를 구하는 문제는 이분탐색인 경우가 많다.
• left값과 right값을 나눠야하는데, 문제는 최소의 시간을 구하도록 요구
  → left 초기값을 1로, right는 입력 배열의 마지막값 * n으로 두어 최대의 시간을 상정하였다.
• 시간이 주어졌을 때 그 시간안에 심사를 할수있는 인원을 구하는 수식 :
  count += mid / times[i] 를 통해 구할 수 있다. (동시적으로 할 수 있기 때문에)
• 단위 주의 : Integer 범위를 초과하기 때문에 연산시 long을 사용해야한다.

어려운점 & 실수

정답

[blossun]

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = (long) n * times[times.length - 1]; //가장 최악의 경우의(오래걸리는) 시간
        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0; // 총 심사한 인원
            for (int i = 0; i < times.length; i++) { //빨리 심사하는 심사관 순으로 심사처리
                sum += mid / times[i];
            }
            if (sum < n) { // 해야할 인원보다 심사처리 못함 -> 시간 더 필요
                left = mid + 1;
            } else { // 해야할 인원보다 심사처리 많이함 -> 시간을 줄여서 더 최고 경우의 시간을 만든다.
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}