[JS] 셔틀버스 (2018 카카오)

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

 

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

프로그래머스

 

 

 

사실 지금생각하면 굳이 이분탐색이 필요할 것 같지는 않고 시뮬레이션을 돌리며 답을 도출해도 될 것 같다.

 

하지만 시간을 구하는 문제가 나올때 이분탐색을 활용하면 훨신 구조적으로 프로그램을 짤 수 있다. 시간이란 데이터는 항상 정렬되어 있기 때문이다.

 

이분탐색을 활용하면 문제접근법 자체는 매우 단순해진다.

 

1. 이분탐색으로 시간 검색

2. 해당 시간에 셔틀을 탈 수 있는지 체크

 

 

우선은 시간을 분단위로 생각하는 것이 편하기때문에 변환을 도와주는 두개의 함수를 만들어준다. 그리고 콘이 해당 시간에 셔틀을 탈 수 있는지 시뮬레이션해주는 함수를 하나 만들어준다. 만약 탈 수 있다면 더 늦은시간쪽으로 검색을 하고 그렇지 않다면 더 이른 시간으로 검색을 하면 된다.

 

 

function solution(n, t, m, timetable) {
    const changehhmmToM = (time) => {
        const [hour,minute] = time.split(":").map(v => +v )
        return hour * 60 + minute
    }
    const changeMTohhmm = (time) => {
        const [hour,minute] = [~~(time/60) , time%60]
        return String(hour).padStart(2,'0') + ':' + String(minute).padStart(2,'0')
    }
    
    const isCanGoCompany = (time) => {
        let pIdx= 0 
        for(let i = 0 ; i < n ; i++){
            const curTime = 9*60 + i * t
            
            let busPassenger = 0 //이번 회차의 버스 승객 수 
            while(busPassenger<m && timetable[pIdx] <= curTime){
                if(time < timetable[pIdx]) return true
                pIdx ++
                busPassenger ++
            }
            //탈수 있다면 회사에 갈 수 있다고 생각
            if(busPassenger<m && time<=curTime) return true
        }
        return false
    }
    
    timetable = timetable.map(v => changehhmmToM(v)).sort((a,b) => a-b)
    
    
    let [left,right] = [0,24*60]
    while(left<=right){
        const mid = ~~((left + right) / 2)
        if (isCanGoCompany(mid)) left = mid + 1
        else right = mid - 1
    }
    
    return changeMTohhmm(left-1)
}