[JS] 프로그래머스 입국심사 풀이

Dev.Jo·2022년 3월 25일
0

알고리즘

목록 보기
18/21
post-thumbnail

풀이 코드

function solution(n, times) {
    let left = 0
    let right = Math.max(...times) * n
    
    while(left < right){
        let mid = Math.floor((left+right)/2)
        if(n <= getSimsaTime(times,mid)){
            right = mid
        } else if(n > getSimsaTime(times,mid)){
            left = mid + 1
        } 
    }
    return right
    
    function getSimsaTime(times,target){
        return times.reduce((acc,cur)=>acc+Math.floor(target/cur),0)
    }
}

풀이

  1. 이진탐색을 해야하는 대상이 숨어있다.

  2. 우리가 구해야하는 정답인 모든 사람이 심사를 받는데 걸리는 시간을 이진탐색해서 찾아야 한다.

  3. 정답의 범위를 좁혀보자
    - 최대: Math.max(...times) * n
    최악의 경우 n명의 사람이 최대시간 입국심사만 받는 경우이다

  4. lower bound를 사용해 target을 구하자

복기

  1. 이진탐색 문제에 익숙하지 않기 때문에, 문제를 처음 봤을 때 이게 왜 이진 탐색 문제이지? 뇌정지가 왔었다

  2. 입국심사를 기다리는 사람이 최대 1,000,000,000명이라는 어마어마한 숫자가 될 수 있기 때문에 시간복잡도 O(logN)의 이진탐색으로 풀이해야한다는 추측이 가능하다

  3. 최소를 구하는 경우 lower bound를 구하자

profile
소프트웨어 엔지니어, 프론트엔드 개발자

0개의 댓글