← All Articles

[PROGRAMMERS] 셔틀버스 - 2018 KAKAO BLIND

Posted on

문제 :

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

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

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

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

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.


입력 형식

셔틀 운행 횟수 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 사이의 값이 될 수 있다.



풀이 :

본 문제는 string 형태로 전달되는 시간 정보를 코드에서 사용하기 쉬운 형태의 자료형으로 변경 후 각 시간 대 버스에 탑승할 수 있는 가장 늦은 시각을 계산해나가면서 해결하는 문제이다.

문자열 처리와 시각 계산 방식만 잘 설계해두고 푼다면 엄청 어려운 문제는 아닌 듯 하다.


[ 세부 구현사항 ]

  • 가장 먼저 string 형태로 전달되는 시간 정보 timetable을 int형 hour, minute으로 다루는 timeFormat 구조체로 변경해 formattable 벡터에 저장한다.
  • timetable 정보들은 시간 순서대로 정렬되어 있지 않기 때문에 formattable 시간 정보를 오름차순으로 정렬한다.
  • curIdx(현재 formattalbe 시간 계산 인덱스 위치), curCnt(현재 시간대 버스에 탑승 예정 사람 수) 두 변수를 활용해서 각 시간대 버스에 탈 수 있는 사람을 게산한다.
  • 현재 시간대 버스 최대 승객 수를 초과하거나 다음 번 사람이 도착한 시간이 버스가 도착한 시간보다 늦을 경우 반복문에서 빠져나온다.
  • 반복문에서 빠져나온 시점에서 curCnt(현재 버스에 탑승할 승객 수)가 최대 승객 수 보다 적을 경우에는 콘이 버스 도착 시간에 도달해도 버스를 탈 수 있기 때문에 최대 탑승 가능 시간에 버스 도착 시간을 저장한다. 하지만 curCnt가 최대 승객 수와 같을 경우에는 콘이 동일 시간에서 가장 뒤에 서기 때문에 가장 늦게 탑승한 승객보다 1분 빠른 시간을 최대 탑승 가능 시간에 저장한다.
  • 이 과정을 셔틀 횟수만큼 반복해주면 답을 도출할 수 있다.


코드 :

코드 보기/접기 
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct timeFormat {
    int hour, minute;
};

bool compare(timeFormat a, timeFormat b) {
    if (a.hour == b.hour) return a.minute < b.minute;
    return a.hour < b.hour;
}

timeFormat changeFormat(string str) {
    return timeFormat{stoi(str.substr(0, 2)), stoi(str.substr(3, 2))};
}

timeFormat calculTime(timeFormat time, int minutes) {
    time.minute += minutes;
    if (time.minute >= 60) {
        time.hour++;
        time.minute -= 60;
    } else if (time.minute < 0) {
        time.hour--;
        time.minute += 60;
    }
    return time;
}

string solution(int n, int t, int m, vector<string> timetable) {
    vector<timeFormat> formattable;
    for (string str: timetable) {
        formattable.push_back(changeFormat(str));
    }
    sort(formattable.begin(), formattable.end(), compare);

    timeFormat curTime = timeFormat{9, 0};
    timeFormat ansTime = calculTime(formattable[0], -1);

    int curIdx = 0, totalIdx = formattable.size();
    while (n--) {
        int curCnt = 0;
        while (curIdx < totalIdx) {
            if (compare(curTime, formattable[curIdx]) || curCnt >= m) { // curIdx time이 더 큰 경우, 못 타는 경우
                break;
            }
            curIdx++;
            curCnt++;
        }

        if (curCnt < m) {
            ansTime = curTime;
        } else {
            ansTime = calculTime(formattable[curIdx - 1], -1);
        }

        if (curIdx >= totalIdx) break;
        curTime = calculTime(curTime, t);
    }
    return ((ansTime.hour < 10) ? "0" + to_string(ansTime.hour) : to_string(ansTime.hour)) + ":"
           + ((ansTime.minute < 10) ? "0" + to_string(ansTime.minute) : to_string(ansTime.minute));
}


AlgorithmalgorithmprogrammersC++