[프로그래머스] 셔틀버스 C++

---

풀이

가장 늦게 버스에 타기 위한 조건은 두 가지이다.

1. 마지막 버스에 자리가 남아있다면
   -> 마지막 버스가 도착하는 시간에 줄을 서면 된다.
2. 마지막 버스에 자리가 남아있지 않다면
   -> 마지막 버스에 마지막으로 타는 크루보다 1분 먼저 줄에 서면 된다.

위 조건을 위해 우리가 필요한 정보는 마지막 버스(n - 1 버스)에 대한 다음의 정보이다.
1. n - 1 버스의 도착시간
2. n - 1 버스에 탑승한 인원 (버스가 가득 찼는지)
3. n - 1 버스에 마지막으로 탄 크루가 대기열에 선 시간

n - 1 버스 전까지는 크루들을 버스에 태워 보내 소거해주면 된다.

크루들을 버스에 태울 때는 다음 같은 경우를 조심해야 한다.

timetable이 ["08:00", "09:09", "09:10"]이고, 버스의 도착시간 t는 10분, 탑승인원 m은 2명이다.

버스는 두명까지 태울 수 있지만 09:00에 도착하는 버스는 08:00에 줄을 선 한 명만 태운채로 떠난다. 버스의 탑승인원이 천명이어도 버스 도착 전에 줄을 선 크루는 한명이기 때문이다.

이러한 조건으로 버스들을 모두 보내고 마지막 n - 1 버스의 정보를 취하면 된다.

n - 1 버스에 자리가 남아있는지, 가득 찼는지에 따라 시간을 반환하면 된다.

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string arrival(int offset) // 버스의 도착시간
{
    string h = to_string(offset / 60 + 9);
    string m = to_string(offset % 60);
    
    string ret = "";
    
    if (h.length() < 2)
        ret = "0" + h + ":";
    else
        ret = h + ":";
    
    if (m.length() < 2)
        ret += "0" + m;
    else
        ret += m;
    
    return ret;
}

string second_to_last(string last) // 마지막으로 타는 크루보다 1분 앞선 시간을 반환
{   
    int d = stoi(last.substr(0, 2)) * 60 + stoi(last.substr(3, 2)) - 1;
    
    string h = to_string(d / 60);
    string m = to_string(d % 60);
    
    string ret = "";
    
    if (h.length() < 2)
        ret = "0" + h + ":";
    else
        ret = h + ":";
    
    if (m.length() < 2)
        ret += "0" + m;
    else
        ret += m;
    
    return ret;
}

string solution(int n, int t, int m, vector<string> timetable)
{
    sort(timetable.begin(), timetable.end());
    int offset = 0; // 09:00 + offset = 다음 버스의 도착시간
    int cur = 0; // 대기열 가장 앞 크루의 인덱스
    string last = ""; // 버스에 마지막으로 탄 크루가 대기열에 선 시간
    int count = 0; // 버스에 탄 인원
    
    for (int i = 0; i < n; ++i) // i번 버스
    {
        string now = arrival(offset);
        count = 0;
        
        for (int j = 0; j < m && cur < timetable.size(); ++j) // i번 버스에 크루들을 태우기 위한 반복문
        {
            if (timetable[cur] <= now)
            {
                last = timetable[cur];
                ++cur;
                ++count;
            }
            else
                break;
        }
        
        offset += t; // 운행간격 t를 더해주어 다음 버스의 시간을 설정
    }
    
    if (count < m) // 마지막 버스에 자리가 남았는지
        return arrival(offset - t);
    else // 마지막 버스가 가득 찼는지
        return second_to_last(last);
}

---

timetable배열은 문자열 "HH:MM" 형식으로 들어오는데 std::string의 비교연산자로 시간을 비교했다. 문제를 풀다보니 timetable을 새로운 정수형배열로 만드는 것이 더 효율적일 수 있겠다고 생각했다.