2018 KAKAO BLIND RECRUITMENT 문제이며 레벨 3으로 구분되어있다.

문제

셔틀버스 도착횟수, 도착간격, 최대탑승인원이 주어지고 대기인원의 시간을 알고있을때 셔틀을 탈 수 있는시간중 가장 늦은시간을 출력하는 문제이다. 시험 당시 정답률이 26.79%였다고 한다.

풀이과정

<입력>

1. 셔틀 횟수 "n"(Number)
2. 셔틀 시간간격 "t"(Number)
3. 셔틀 최대탑승인원 "m"(Number)
4. 다른사람들 대기열도착시간 "timetable"(Array)

<시간을 표시하는 방법>

우선 다른건 다 제쳐두고 입력에서 주어진 "hh:mm"형식의 string으로는 데이터를 제대로 사용할 수 없을것 같았다. 모든 시간을 간단한 Number 형태로 통일하여 나타내는 아이디어가 필요했다.
그래서 "hh:mm"을 "n"분(minute)형태로 고치기로 했는데 주어진 입력 기준으로 (hh*60+mm) 계산을 해주면 간단한 일이었다.

    let time = timetable.map(v=>v.split(":").map(v=>+v)).map(v=>v[0]*60+v[1]).sort((a,b)=>a-b)
            //":"기준으로 나누고 숫자로 바꿔주고 시간에 60을 곱하고 분을 더한다. 도착 순서대로 정렬도 해준다.

셔틀 도착 시간도 현재는 도착 횟수, 간격으로 정보가 제공되어있는데 직관적으로 숫자로 도착시간 배열을 만들겠다.

    let arrive = new Array(n).fill(0).map((v,i)=>540+t*i)
      //셔틀 첫 도착시간이 9시(540분)으로 고정이므로 540부터 t씩 늘려가면서 n번 도착하는 배열을 만든다 

<무조건 마지막 셔틀에 타면 된다>

처음에는 안일하게도 마지막 셔틀 대기시간동안 도착한 사람만 filter해서 그중에 m(최대탑승인원)명 안에 들면 된다고 생각했었다.

let answer=0
let last = time.filter(v=>v>arrive[arrive.length-2]&&v<=arrive[arrive.length-1])
                  //마지막 직전 셔틀 출발한 이후부터 마지막 셔틀 도착할때까지 도착한 사람들을 추려서

if(last.length<m){                //기다리는 사람이 m명 이하면
answer=arrive[arrive.length-1]    //마지막 셔틀 도착시간에 맞춰 도착하고
} else{                           //기다리는 사람이 m명보다 많으면
answer = last[m-1]-1              //m명째(index기준으론 (m-1)index)사람보다 1분 빨리오면 된다.
}

그런데 생각해보니 이전에 기다리고있던 사람들이 무조건 다 탄다는 보장이 없었다. 지금까지 도착한 셔틀 탑승인원보다 기다리던 사람이 많으면 직전 셔틀이 출발하고도 남아있는 사람이 있을 수 있다는 뜻이다.
결국 처음부터 끝까지 셔틀 탑승 상황을 체크해줘야 할 것 같다.

<정류장의 코드화>

셔틀이 도착할 때 마다 몇 사람이나 탈 수 있을까?
셔틀이 도착할 때 마다 해당셔틀 도착시간 이전에 기다리던 사람들을 추려서
기다리던 사람이 m보다 크면 m만큼만 탑승하고
탑승한 사람 수 만큼 대기열 앞에서부터 잘라주면 될것이다.

    for(let i=0;i<arrive.length-1;i++){            //마지막 직전셔틀까지
        let waiting =time.filter(v=>v<=arrive[i])  //도착시간 이전에 기다리던사람을 추려서
        let cut = waiting.splice(0,m)    //m명만큼 잘라주면 되는데
                                         굳이 splice가 아니라 변수를 만들어서 waiting 길이가 m보다 길면 m, 
                                         아니면 waiting의 길이를 반환하도록 하면 더 시간이 절약될것 같다
        time.splice(0,cut.length)        //탑승한 인원만큼 대기열에서 빼주는 과정  
    }

이 과정을 끝내주면 마지막 직전 셔틀이 출발하고 남은 인원 및 도착할 인원이 time 배열에 남게 된다.

<마지막 셔틀 타기>

이제는 마지막 셔틀이 올때 기다리고 있을 사람 중 m번째보다 1분이라도 빨리오면 되는것이다.
time배열에는 마지막 셔틀 출발시간보다 늦게오는 의미없는 사람도 있으므로 해당 인원은 제외해주고 계산해준다.

    let answer=0   
	let lastBus = arrive[arrive.length-1]       //마지막 셔틀 출발시간
    let remain = time.filter(v=>v<=lastBus)     //마지막셔틀 출발 전에 도착할 인원들
    if(remain.length<m){                        //탑승예정 인원이 m보다 작으면
        answer=lastBus                          //마지막셔틀 출발시간 맞춰오면 된다.
    }else{                               
        answer=remain[m-1]-1                    //아니면 탑승예정인원중 m번째 인원보다 1분 빨리오면 된다.
    }

<정답 출력-분을 시간으로>

이제 answer에는 시간*60+분 으로 나타낸 시간이 저장되어있는데 출력 형식은 "hh:mm"형태여야하므로 다시 역순으로 변경해줄 필요가 있다.

    let hour = Math.floor(answer/60).toString().padStart(2,"0") //분을 60으로 나눈 몫이 시간 나머지는 분이된다.이된다
    let min = (answer%60).toString().padStart(2,"0")            //각각 문자열로 바꾸준 후 1자리수라면 앞에 0이 붙도록 해준다.
=
    return `${hour}:${min}`

결과는?

크게 많이 어려웠던 문제같지는 않은데 정답률 보고 조금 의외였던 문제였다. 나도 운이 좋게 방향을 잘잡아서 풀 수 있었던 것일까. 반대로 방향이 꼬이기 시작하면 정답률 높은 문제를 내가 틀릴 수도 있는 일이다. 여러가지 문제를 풀어보고 문제 방향잡는 감을 키우는 것이 중요할 것이다.

전체코드

function solution(n, t, m, timetable) {
    let time = timetable.map(v=>v.split(":").map(v=>+v)).map(v=>v[0]*60+v[1]).sort((a,b)=>a-b)
    let arrive = new Array(n).fill(0).map((v,i)=>540+t*i)

    for(let i=0;i<arrive.length-1;i++){
        let waiting =time.filter(v=>v<=arrive[i])
        let cut = waiting.splice(0,m)
        time.splice(0,cut.length)
    }

    let lastBus = arrive[arrive.length-1]
    let remain = time.filter(v=>v<=lastBus)
    let answer=0
    if(remain.length<m) answer=lastBus
    else answer=remain[m-1]-1

    let hour = Math.floor(answer/60).toString().padStart(2,"0")
    let min = (answer%60).toString().padStart(2,"0")

    return `${hour}:${min}`
    }