[JS] 셔틀버스 - 시간을 비교할땐 항상 조심하자!

2018년 카카오 채용에 있었던 문제입니다.문제도 뭔가 요즘처럼 복잡하지도 않고 직관적입니다.다만, 케이스 분류할 때 조심해야할 점들이 몇몇 가지 있어서 같이 이야기해보면 좋을 것 같습니다.자 같이 볼까요?

---

문제 요약

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

 

입력 형식

 

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

 

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

 

테스트케이스

n	t	m	timetable	answer
1	1	5	["08:00", "08:01", "08:02", "08:03"]	"09:00"
2	10	2	["09:10", "09:09", "08:00"]	"09:09"
2	1	2	["09:00", "09:00", "09:00", "09:00"]	"08:59"
1	1	5	["00:01", "00:01", "00:01", "00:01", "00:01"]	"00:00"
1	1	1	["23:59"]	"09:00"
10	60	45	["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]	"18:00"

 

접근 방법

접근 방법이 딱히 어렵진 않습니다.

직관적으로 방법이 딱 하고 떠오르는 그 방법대로 가시면 됩니다.

전 이런 순서대로 한 번 해볼까 합니다.

 

순서

1. timetable을 내림차순으로 정렬해 stack 구조에 저장한다.
2. 셔틀버스의 운행 횟수 n > 0 이고, stack.length > 0 일때 루프를 돌린다.
    1) 셔틀 버스의 정원 m 을 기준으로 루프를 돌린다.
        (1) stack에서 pop을 한다.
        (2) pop한 값과 현재 셔틀 버스의 도착 시간을 비교한다.
        (3) pop한 값이 도착시간보다 크다면 다시 stack에 push해준다.

    2) 결과로 return할 시간과 분을 적절히 조정해준다.
    3) 셔틀 버스 도착시간을 t에 맞춰서 적절히 조정해준다.

 

적다보니 뭔가 복잡한데,

나머지는 입맛대로 해주셔도 좋고 이 문제가 물으려는 가장 핵심적인 것은

시간을 비교할 수 있는가? 라고 생각합니다.

 

프로그래머스

 

이건 제가 올린 질문 겸 팁인데요. 한번 보시면 좋을 것 같습니다.

 

정답 코드

function makeDate(hour, minutes) {
    let hourString = hour.toString();
    let minutesString = minutes.toString();
    hourString = "0".repeat(2 - hourString.length) + hourString;
    minutesString = "0".repeat(2 - minutesString.length) + minutesString;
    return `${hourString}:${minutesString}`;
}

function solution(n, t, m, timetable) {
    const stack = timetable.sort().reverse();
    let stage = n;
    let waitTime = t;
    let [shuttleHour, shuttleMin] = [9, 0];
    let [resultHour, resultMin] = [0, 0];
    
    while (stack.length > 0 && stage > 0) {
        let passengers = 0;
        let [currWaitHour, currWaitMin] = [0, 0];
        for (let i = 0; i < m; i++) {
            if (stack.length === 0) break;
            [currWaitHour, currWaitMin] = stack.pop().split(":").map(v => Number(v));
            const firstWaitTime = Number(`${currWaitHour}${currWaitMin < 10 ? "0" : ""}${currWaitMin}`);
            const shuttleTime = Number(`${shuttleHour}${shuttleMin < 10 ? "0" : ""}${shuttleMin}`);
            if (firstWaitTime > shuttleTime) {
                stack.push(makeDate(currWaitHour, currWaitMin));
                break;
            } else {
                passengers++;
            }
        }
        if (passengers < m) {
            [resultHour, resultMin] = [shuttleHour, shuttleMin];
        } else {
            [resultHour, resultMin] = [currWaitHour, currWaitMin];
            if (currWaitMin - 1 < 0) {
                [resultHour, resultMin] = [resultHour - 1, 59];
            } else {
                [resultHour, resultMin] = [resultHour, currWaitMin - 1];
            }
        }
        
        shuttleMin += waitTime;
        if (shuttleMin > 59) {
            shuttleMin -= 60;
            shuttleHour++;
        }
        stage--;
    }
    return makeDate(resultHour, resultMin);
}

 

결과

 

팁 1. makeDate

function makeDate(hour, minutes) {
    let hourString = hour.toString();
    let minutesString = minutes.toString();
    // 1시부터 9시까지는 앞에 0을 붙혀줘야합니다.
    hourString = "0".repeat(2 - hourString.length) + hourString;
    // 0분부터 9분까지는 앞에 0을 붙혀줘야합니다.
    minutesString = "0".repeat(2 - minutesString.length) + minutesString;
    return `${hourString}:${minutesString}`;
}

 

0을 적절하게 잘 붙혀주는게 팁입니다.

문제가 원하는대로 0을 붙혀줍시당

 

팁 2. 시간 비교하는 부분

const firstWaitTime = Number(`${currWaitHour}${currWaitMin < 10 ? "0" : ""}${currWaitMin}`);
const shuttleTime = Number(`${shuttleHour}${shuttleMin < 10 ? "0" : ""}${shuttleMin}`);
if (firstWaitTime > shuttleTime) {
    stack.push(makeDate(currWaitHour, currWaitMin));
    break;
} else {
    passengers++;
}

 

역시 분 앞에 0을 붙혀줘야합니다.

사실 이렇게 안하고 시간끼리 먼저 비교해주고, 그 다음 분을 비교하면 이런걸 안써도 됩니다.

전 셔틀버스 시간보다 미리 와있는 사람들은 외부에 passengers라는 변수를 1씩 키워주면서 세줬습니다.

이걸로 결과값을 적절히 조정해줍시다.

 

 

팁3. 결과값 조정하는 부분

if (passengers < m) {
	// 셔틀버스 자리가 남네요. CON이 셔틀버스 시간 맞춰와도 되겠습니다.
    [resultHour, resultMin] = [shuttleHour, shuttleMin];
} else {
	// 셔틀버스가 다 찼네요. 마지막 사람보다 1분 빨리 옵시다.
    [resultHour, resultMin] = [currWaitHour, currWaitMin];
    if (currWaitMin - 1 < 0) {
        [resultHour, resultMin] = [resultHour - 1, 59];
    } else {
        [resultHour, resultMin] = [resultHour, currWaitMin - 1];
    }
}

 

적절히 조정해줍시다!

조심하셔야 할 부분은 0분에서 1분 빼주면 시간도 1빼주고 59분으로 넣어줍시다.

조건에서 전날부터 기다릴 일은 없다고 하니, 0시 0분에서 1분이 빠질 일은 없겠네요.

 

항상 시간비교할 때는 0분에서 9분까지, 그리고 1시부터 9시까지와 10시부터 12시까지 반영해서 다 비교가 가능한지 알아보는 습관을 가지도록 합시다!

 

그럼 이만!