[이분탐색] 입국심사

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

 

첫 풀이 (성공)

1. 최소, 최대로 걸리는 시간의 중간시간을 구한다.
2. 중간시간보다 시간이 더 필요하면 최소시간을 늘리고 다시 중간시간을 찾는다
3. 중간시간보다 시간이 남으면 최대시간을 줄이고 다시 중간시간을 찾는다
4. 2,3번을 최소시간과 최대시간이 엇갈릴 때까지 반복한다

 

주의할 점

최소값을 구해야하니까 minTime을 리턴하게

시간이 부족한 경우에만 minTime을 늘리고

그 외는 maxTime을 줄인다.

 

최소시간 = 최대시간이라고 최소시간을 찾은게 아니다.

최소시간이 늘어나서 최대시간이랑 같을 수 도 있기때문이다

따라서 최소시간과 최대시간이 엇갈릴 떄까지 찾는다

 

function solution(n, times) {
    var answer = 0;
    let minTime = 0;
    let maxTime = Math.max(...times) * n;
    
    while(minTime <= maxTime) {
        let midTime = Math.floor((minTime + maxTime) / 2);
        let finishedCount = 0; // 심사완료한 사람수
        
        // 시간안에 심사완료할 수 있는 사람수 
        for (const time of times) {
            finishedCount += Math.floor(midTime / time);
        }
        // if (n === finishedCount) {
        // 딱 맞춰서 완료했어도 좌우로 움직일 수 있다
        // }
        
        // 최소값을 구해야하니까 minTime을 리턴하게
        // 시간이 부족한 경우에만 시간을 늘린다.
        if (n > finishedCount) {
            minTime = midTime+1;
        } 
        // n보다 "같거나" 큰 경우 시간을 줄인다 (같은경우를 시간을 줄이는 곳에 배치)
        else {
            maxTime = midTime -1;
        }
    }
    return minTime;
}