입국심사(프로그래머스-이분탐색)

문제

코드

class Solution {
    public long solution(int n, int[] times) {
        int minTime=Integer.MAX_VALUE;
        for(int t:times)
            minTime=Math.min(minTime,t);    
        long start=1;
        long end=(long)minTime*n;
        long mid=(start+end)/2;
        
        while(start<=end){
            mid=(start+end)/2;
            long possibleNum=0;
            for(int t:times)
                possibleNum+=mid/t;
            if(possibleNum<n) start=mid+1;
            else end=mid-1;
        }
        return start;
    }
}

풀이

(1) 전체적인 로직은 이분 탐색을 통해 걸리는 최소 시간을 찾는 것이다. 이분탐색을 하기 위해서는 start와 end를 설정해주어야 한다. 문제 상 나올 수 있는 가장 작은 시간은 1분이다. 그리고 걸리는 시간의 최댓값은 한 심사관이 모든 사람을 심사하는 경우이다. 이 때 기준으로 할 심사관은 아무나 골라도 되지만, 나는 end의 범위를 최소화 하기 위해서 걸리는 시간이 가장 짧은 심사관을 기준으로 end를 정했다.
(2) 이분탐색을 실시한다. mid는 검사할 시간이다. 이 시간 안에 모든 사람이 통과할 수 있는지 확인하는 것이다. 문제에서 제시한 입출력 예시로 살펴보면 7분,10분 검사관이 있다.
ex) 만약 mid가 30분일 때 모든 사람을 처리 할 수 있는가를 검사
-> 30/7+30/10=7 -> 총 7명을 30분 안에 심사할 수 있다.

위 방식으로 심사할 수 있는 사람 수를 계산한다.
그리고, 심사할 수 있는 사람 수가 n보다 작으면 start=mid+1이 되고, 심사할 수 있는 사람 수가 n보다 크거나 같으면 end=mid-1 로 하고 다시 이분 탐색을 실시한다.

(3) 위 방식으로 이분탐색을 종료하면, start는 모든 사람을 심사할 수 있는 가장 짧은 시간이 된다.

결과

코드를 보면 정말 간단한 이분탐색 문제처럼 보인다.
하지만 난 이런문제가 다시 나오면 풀 자신이 없다.
문제를 보고, 아무리 봐도 이건 그리디가 아니면 풀 방법이 없는 것처럼 보였다. 하지만 또 제한사항을 보면 분명 그리디로 풀면 시간초과가 날 것이 뻔했다.
그리고 문제 유형이 이분탐색이라 이분 탐색 문제인 것을 알고는 있었지만, 도대체 이걸 어떻게 이분 탐색으로 풀어야 할지 감도 안왔다.

다른 사람의 풀이를 참고 했고, 이해하는 것도 조금 시간이 걸렸다.
시간을 탐색해서 그 시간안에 몇 명을 심사할 수 있는지 검사하면서 최적의 시간을 찾아나간다는 생각을 도대체 어떻게 할 수 있는건지 신기하다.

그리고 이분탐색으로 문제를 풀고, 분명 문제가 없다고 생각했는데, 몇 개의 테스트 케이스를 통과하지 못했다.
문제는 long end=(long)minTimen; 이 코드가 문제였다.
이렇게 minTime을 업캐스팅 해주지 않으면,
minTime(int)n(int) 이기 때문에, 연산값이 int의 범위를 넘어가버리면 짤리게 된다.
그래서 둘중 하나를 long형으로 업캐스팅 시킨 후, 계산을 해주어야 한다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges