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

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

입국심사
문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.
입출력 예

입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

문제 풀이 힌트 

기다리는 N명이 심사를 다 하는데 걸리는 시간 중 최솟값을 우리는 구해야 한다. 

이 최솟값은 0분이상 60분 이하의 값일 것이다. 

0분은 당연히 알 것이고 

60분는 어떻게 나왔을까? 

주어진 times 배열중 가장 오래 걸리는 심사관한테 N명 모두가 심사를 받는 값이 된다 

즉, 6명 모두가 미쳐서 제일 오래걸리는 심사관 한테 받아서 6 * 10 분  = > 총 60분이 걸릴 때이다. 

 

그림으로 표현하면 이렇게 되고, 

이분탐색을 이용한다는 건 뭘까? 

left 값을 서서히 오른쪽으로, 

right 값을 서서히 왼쪽으로 이동시켜 

결국 최솟값을 찾는 방법일 것이다. 

 

대신 mid 값을 사용해줄 것이다 ! 

left와 right의 중간값은 어떻게 구할까? left + right 을 나누기 2하면 된다. (Math.floor를 이용해서 내림 값으로 할 것 !)

30분동안

=> 7분 걸리는 심사관한테는 4명이 심사를 완료할 수 있다. 

=> 10분 걸리는 심사관한테는 3명이 심사를 완료할 수 있다. 

그럼 총 7명!

우리가 제시받은 N = 6 보다 큰 숫자다. 

그럼 최솟값이 30분보다 왼쪽 범위에 있다는 걸 알 수 있다. 

우리의 범위는 밑 그림 처럼 좁혀진다. 

 

그럼 ? right 값을 mid보다 -1 값으로 지정하면 되겠다. 

즉, 우리가 구한 mid 시간에서 심사를 완료할 수 있는 사람 수가 >  N 보다 크면 right 값을 mid - 1 로 지정해주고 

mid 시간에서 심사를 완료할 수 있는 사람수  < N 라면 , left 값을 mid + 1로 지정해주면된다.  

 

 

그럼 다음 mid 값은 뭘까? =>  Math.floor((0+ 29)/2)

이런식으로 반복해주면 된다 ! 

그러다보면 left = 28 , right = 29 일때가 오고,, 이때의 mid 값은 28이 된다. 

 

 

mid = 28일 때, 심사를 완료할 수 있는 사람 수는 6명이다 !

N과 같은 수다 

그럴 땐 어떻게 해야하나?? 

right을 mid - 1로 지정해준다. 그리고 그때의 left 값이 답이 된다. 

따라서 지금까지 이 모든 것들의 반복을 이 조건에 해당될 때만 가능하게 해 줄 것이다. ! 

while(left <= right){

//여기에 코드로 작성

}

그럼 right이 left보다 작을 때의 left 값이 우리가 구할 최솟값이 된다 ~~!! 

정답 풀이 코드 

function solution(n, times) {
    let sorted = times.sort((a,b) => a-b); 
    let left = 0; 
    let right = n * times[times.length-1]; 

    while(left <= right){
        let cntPeople = 0; 
            let mid = Math.floor((left+ right) /2);
        for(let i=0; i<times.length; i++){
            cntPeople += Math.floor(mid / sorted[i]); 
        }
 
        if(n <= cntPeople){
                right  = mid -1; 
        }else if(cntPeople < n){
            left = mid +1; 
        }
    }
    return left
}

의사 코드 추가 

function solution(n, times) {
    let sorted = times.sort((a,b) => a-b); //심사관 오름차순 정렬
    let left = 0; 
    let right = n * times[times.length-1]; //가장 느린 심사는 맨 마지막에 위치해있다. 

    while(left <= right){ 
        let cntPeople = 0; //우리가 구하는 mid 시간에서 심사를 완료할 수 있는 사람 수다.  
            let mid = Math.floor((left+ right) /2);
        
        //우리가 정렬한 심사관 sorted 에서 정해진 시간내  심사 완료 사람 수 각각 구해서 누적
        for(let i=0; i<times.length; i++){
            cntPeople += Math.floor(mid / sorted[i]); 
        }
 
        if(n <= cntPeople){ // n과 같을 때, n보다 클 때 rigth 값을 mid 의 왼쪽에 둬 범위를 좁힌다. 
                right  = mid -1; 
        }else if(cntPeople < n){
            left = mid +1; 
        }
    }
    return left
}