프로그래머스 연습문제이며 레벨3 문제이다.

문제

풀이과정

<입력>

1. 입국심사를 기다리는 사람 수 "n"(Number)
2. 심사관마다 한명 심사하는데 걸리는 시간 "times"(Array)

<문제 단순화>

주어진 조건에서 n명을 심사하는데 걸리는 시간을 알기는 어렵지만 시간이 주어졌을 때 그동안 몇명을 심사했는지 아는 것은 쉬운일이다.
각 심사관 별로 주어진 시간을 걸리는 시간으로 나누면 되고 남는 시간은 아직 심사가 완료되지 않았을터이므로 버려주면 된다

t(주어진시간) 동안 심사한 사람의 수 = Math.floor(t(주어진시간)/time(걸리는시간))

<이분탐색>

주어진 조건의 숫자가 너무 크기 때문에 O(n)의 시간복잡도 조차도 부담이될 수 있다. 이분탐색을 통해 답에 최대한 효율적으로 도달할 필요가 있다.

    let left = 1;    //left = 예상가능한 최소값. 효율성을 위해 times중 최소값 정도 넣어줘도 상관은 없다.
    let right = Number.MAX_SAFE_INTEGER   //right = 예상가능한 최대값. 
    let mid = Math.floor((left+right)/2); //left와 right의 중간값. 여기서는 테스트할 주어진 총 시간을 의미한다.

    while(left<right){                    //left가 right와 같다는 것은 답을 찾았다는 것을 의미

       let people = times.reduce((a,b)=>a+Math.floor(mid/b),0) //각 심사관별로 주어진 시간에 심사할 수 있는 인원 수를 모두 더해준다.

       if(people>=n) right = mid     //해당 시간에 우리가 원하는 사람보다 같거나 많이 심사했으면
                                        최대값을 현재값으로 세팅(mid값 감소)
                                       
        else left = mid+1;           //우리가 원하는 사람보다 적게 심사했으면
                                       최소값을 현재값+1로 세팅(mid값 증가)
                                      
         mid = Math.floor((left+right)/2) //mid는 다시 left와 right의 중간값으로
    }
        return mid

<floor? ceil?>

이분탐색중 가장 간단한 형태의 문제가 아닐까 싶은데 한가지 확실히 확인해보고 넘어가고싶은 부분이 있다.
mid를 계산할 때 Math.floor를 쓰느냐 아니면 Math.ceil을 쓰냐 하는것이다.

주어진 시간(mid)에 검사완료할 수 있는 총 인원(people)을 계산했을 때 우리가 원하는 숫자(n)보다 작다면 그 mid는 답이 절대 아니라는것을 알 수 있다.
하지만 people과 n이 같다면 그 때의 mid는 무조건 답일까?

이번 문제의 테스트케이스의 정답인 28분이 주어지면 기다리고있는 6명이 모두 검사를 받을 수 있다.

하지만 mid가 28분이 아니라 29분이면 어떨까?
29분이 지나도 여전히 검사 가능한 최대 인원은 6명이다.
people = n이 나왔지만 그때의 mid를 답으로 반환하면 오답이 되는것이다.

따라서 해당 mid는 right값에 남겨두고 (right=mid) 그 아래의 mid 중 답이 나왔을때 계속 갱신해줘야 후보가 되는 mid값 중 최소값을 고를 수가 있게된다.

따라서 조건에 맞는 mid값중 최소를 선택하고싶으면 Math.floor / right=mid / left=mid+1
조건에 맞는 mid값 중 최대를 선택하고 싶으면 Math.ceil / right=mid-1 / left = mid
로 조건을 걸어줘야하겠다.

<전체코드>

    let left = 1; 
    let right = Number.MAX_SAFE_INTEGER  
    let mid = Math.floor((left+right)/2);
    while(left<right){ 
       let people = times.reduce((a,b)=>a+Math.floor(mid/b),0)
       if(people>=n) right = mid                                 
        else left = mid+1;  
         mid = Math.floor((left+right)/2)
    }
        return mid