[JS/LV3]입국 심사

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

프로그래머스

 

 

 

 

카테고리가 이분 탐색으로 되어있기 때문에 이분 탐색으로 풀었다.

 

문제 요건

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

 

문제 요건은 위와 같다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 할 수 있다면, 한 심사관이 모든 사람을 담당할 수 있는 걸 생각해야 한다. 또한, 동 시간에 여러 명의 심사관이 심사를 할 수도 있다.

그렇기 때문에 times와 같은 길이의 배열을 만들어서 for문으로 계속 돌려가며 시간을 계산하기 보다는(이미 실패한 풀이^^...), 해당 시간을 이분탐색으로 찾아가는게 더 나은 방법같아 그렇게 풀었다.

 

문제 풀이

문제를 풀때 times는 이미 오름순으로 정렬이 되어있기 때문에 정렬을 신경쓰지 않아도 된다,

 

left는 1명의 사람은 반드시 존재하고, 1명의 심사관 또한 반드시 존재하기 때문에, times배열의 0번째 값으로 설정했다

right는 배열의 0번째 값이 제일 작아 다 거기로 몰릴 수 있는 경우를 생각해서 사람수* times배열의 0번째 값으로 설정했다

let left=times[0]
let right=times[0]*n

 

while 문 안의 for 문에서는 times배열을 순회하면서 중간값(시간)을 배열값(심사에 걸리는 시간)으로 나눈 몫을 더하면서 총 합이 사람 수 보다 많게 될 경우는 순회를 중단시키고 right의 값을 중간값으로 설정,

몫이 사람수보다 적을 경우는 left를 중간값+1로 설정하였다

    while(left<right){
        let mid=Math.floor((left+right)/2)
        let total=0
        for(let time of times){
            if(total>=n){
                break
            }
            total+=Math.floor(mid/time)
        }
        if(total>=n){
            right=mid
        }else{
            left=mid+1
        }
    }

 

이렇게 될 경우, total이 n을 충족하는 시간의 최소값을 얻을 수 있게 된다.

최종코드

function solution(n, times) {
    let left=times[0]
    let right=times[0]*n
    while(left<right){
        let mid=Math.floor((left+right)/2)
        let total=0
        for(let time of times){
            if(total>=n){
                break
            }
            total+=Math.floor(mid/time)
        }
        if(total>=n){
            right=mid
        }else{
            left=mid+1
        }
    }
    return left
}