[JS] 입국심사

이분탐색을 활용하여 해결하였다.

 

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

프로그래머스

 

 

이렇게 케이스가 10억명이 넘어가는 특수한 문제들은 대부분 이분탐색을 활용해서 푸는 방법을 생각해야 한다.

시간이라는 데이터는 이미 오름차순이 되어있는 데이터라고 생각할 수 있으므로 시간을 도출해 내는것이 아닌 시간을 하나씩 대입하여 해당 시간안에 사람을 모두 통과시킬 수 있는지 체크하는 방식으로 접근하면 쉽게 해결할 수 있다.

 

 

조금 주의할점으로는 한 사람이 검사할 수 있는 최대 시간또한 10억분이 걸릴 수 있으므로 BigInt 처리를 해주는 것이 필요하다.

 

 

이번 문제는 특히 JS의 특성을 활용해서 간결하게 작성하기 좋은 문제였던 것 같다. 구조분해 할당, 화살표함수 , reduce등 활용하여 최대한 숏코딩을 해보았다. ( 읽기 좋은 코드는 아닌거 같기도 하다 그래도 멋있잖아)

 

 

 

function solution(n, times) {
    //첫 시작값을 최대 시간값 * n으로 잡아서 넉넉하게 둠
    let [start,end] = [0n , BigInt(n * Math.max(...times))]
    
    //time분안에 손님들을 전부 처리할 수 있는지 검사
    const isCanPass = (time) => 
        times.reduce((a,c) => a + ~~(time/BigInt(c)),0n) >= n ? true : false
    
    //이분탐색
    while(start <= end){
        const mid = ~~((start + end) / 2n)
        if(isCanPass(mid)) end = mid - 1n
        else start = mid + 1n
    }
    return start
    
}

 

 

끄읏 -!