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

문제

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

---

풀이(20분)

import java.util.Arrays;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = times[times.length-1] * (long)n; //최악의 경우
        
        while(left <= right) {
            long mid = (left + right) / 2;
            long complete = 0;
            for (int i = 0; i < times.length; i++)
                complete += mid / times[i];
            if (complete < n)
                left = mid + 1;
            else {
                right = mid - 1;
                answer = mid;
            }
        }  
        return answer;
    }
}

 

이분탐색이라는 힌트를 통해 문제를 접근하지 않았다면 다소 어려울 수도 있었다고 생각한다.

풀이 과정은 다음과 같다.

 

1. 입국 심사관의 해결 속도를 먼저 오름차순으로 정렬한다.

2. 최악의 경우 제일 오래 걸리는 심사관으로부터 n명이 모두 검사받게 되는 경우이다. (이를 이분탐색의 right로 정한다.)

3. left <= right인 동안 중간값의 시간에 대하여 한 입국 심사관이 몇명까지 해결할 수 있는지 계산한다.

4. 해결된 값이 모자란다면 시간을 더욱 늘리기 위해 left를 mid + 1로 재설정한다.

4 - 1. 해결값이 크거나 같다면 정답에 이를 저장하고, 더 나은 탐색이 없나 찾기 위해 right = mid - 1로 재설정한다.

 

이분탐색을 떠올리기 힘들 수도 있었던 문제였다고 느낀다. 이분탐색을 효율적으로 사용할 수 있는 방식에 대해 더 연습해야겠다고 느꼈다.