(프로그래머스 c++ KAKAO)셔틀 버스

문제 설명

셔틀버스

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

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

• 셔틀은 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 사이의 값이 될 수 있다.

입출력 예제

ntmtimetableanswer

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

 

시간 계산을 쉽게 하기 위해 분으로 단위를 맞췄다.

start_t = 540 // 셔틀버스 출발 시간인 09:00

wait_t = 0 // timetable에 해당하는 시간

wait_h, wait_m = 0 // wait_t를 계산하기 위해 사용하는 변수

keep은 for문을 탈출하기 위해 사용하는 flag.

 

우선 timetable을 내림차순으로 정렬을 한다.

그리고 뒤에서부터 꺼내서 pop을 하는 형식으로 timetable을 이용한다.

 

for문을 통해 n회만큼 반복하고,

count는 m명보다 작은만큼 while문을 돌도록 한다.

 

timetable이 비어있으면 탈 수 있는 사람이 아무도 없다는 것을 나타내므로

start_t = 540 + (n - 1) * t를 넣어주고, keep = false로 바꿔준 후 while문과 for문을 탈출하여 정답을 리턴하도록 한다.

 

비어있지 않다면 계산을 진행한다.

만약 wait_t <= start_t이면 탈 수 있는 버스인지 확인을 해야 한다.

i == n - 1 && count == m - 1이라면

콘이 타야 하는 버스를 나타내므로 start_t = wait_t - 1을 하여 콘이 1분 먼저 대기하도록 한 후 반복문을 모두 탈출한다.

그렇지 않다면 count++을 해주고, 해당 시간을 pop 해주어 계속 진행하면 된다.

 

만약 wait_t > start_t라면 start_t를 늘려줘야 한다.

하지만 i == n - 1이라면 해당 버스를 타야 하므로 start_t = 540 + (n - 1) * t를 해주고 모든 반복문 탈출.

아니라면 start_t += t를 해주어 계속 진행하면 된다.

 

start_t가 int형이므로 answer에 넣어주기 위해서는 string형태로 바꿔줘야 한다.

또한 자릿수를 확인하여 1자리 수라면 "0"을 시, 분 앞에 넣어주도록 하면 된다.

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    int start_t = 540, wait_t = 0, wait_h = 0, wait_m = 0;
    int count = 0;
    bool keep = true;
    
    sort(timetable.begin(), timetable.end(), greater<string>());
    
    for(int i = 0; i < n; i++)
    {
        count = 0;
        
        while(count < m)
        {
            if(!timetable.empty())
            {
                wait_h = stoi(timetable.back().substr(0, 2));
                wait_m = stoi(timetable.back().substr(3, 2));
                wait_t = (60 * wait_h) + wait_m;
                
                if(wait_t <= start_t)
                {
                    if(i == n - 1 && count == m - 1)
                    {
                        start_t = wait_t - 1;
                        keep = false;
                        break;
                    }
                    else
                    {
                        count++;
                        timetable.pop_back();
                    }
                }
                else
                {
                    if(i == n - 1)
                    {
                        start_t = 540 + (n - 1) * t;
                        keep = false;
                        break;
                    }
                    start_t += t;
                    break;
                }
            }
            else
            {
                start_t = 540 + (n - 1) * t;
                keep = false;
                break;
            }
        }
        if(keep == false)
            break;
        
        if(count == m)
            start_t += t;   
    }
    
    if(start_t / 60 < 10)
        answer = "0" + to_string(start_t / 60);
    else
        answer = to_string(start_t / 60);
    
    answer += ":";
    
    if(start_t % 60 < 10)
        answer += "0" + to_string(start_t % 60);
    else
        answer += to_string(start_t % 60);
    
    return answer;
}