[프로그래머스 lv3] [1차] 셔틀버스 풀이

해설

콘이 셔틀을 타기 위해 나갈 수 있는 가장 늦은 시간을 구하는 문제이다.

 

일단, 모든 크루들의 대기 시간을 정렬하고, 각 시간대별 셔틀에 한명씩 태운다.

이 때, 콘은 가장 마지막 버스에 타야 한다. 따라서, 마지막 셔틀까지 크루들을 태웠을 때, 버스의 정원이 남는다면 가장 늦게 나가도 마지막 버스를 탈 수 있으므로 정답은 마지막 버스의 도착 시간이 된다. 반면, 정원이 다 찬 경우, 콘은 마지막으로 탄 사람보다 1분 먼저 나와야 버스에 탈 수 있으므로 정답은 마지막에 탄사람의 대기시간-1분이 된다.

 

팁

문자열이 특정 포맷으로 이루어져있을 때 sscanf() 함수를 사용하면 값을 쉽게 추출할 수 있다.

특정 포맷으로 문자열을 만들어야 할 때 sprintf() 함수를 이용하면 쉽게 문자열을 만들 수 있다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

string solution(int n, int t, int m, vector<string> timetable) {
    
    //timetable 시간을 정수로 변환
    vector<int> vperson;
    for (auto s : timetable) {
        int a, b;
        sscanf(s.c_str(), "%d:%d", &a, &b);
        vperson.push_back(a*60+b);
    }
    sort(vperson.begin(), vperson.end());

    //1번 차 부터 n번 차까지 크루 태우기
    int i = 0, sz = vperson.size(), ans = 0;
    for (int ncar=1; ncar<=n; ncar++) {
        int cnt = 0;
        int arrivet = 9*60+(ncar-1)*t; //셔틀 도착 시간
        while (i < sz && vperson[i] <= arrivet && cnt < m) { // 셔틀 도착 내에 온 사람 태우기
            cnt++;
            i++;
        }
        if (ncar == n) { //마지막 차
            if (cnt < m) ans = arrivet; //정원이 다 차지 않았다면 셔틀이 오는 시간에 나가야 함
            else ans = vperson[i-1]-1; //정원이 다 찼다면 마지막 사람 이전 시간에 나가야 함
        }
    }
    
    char tmp[50];
    int l = sprintf(tmp, "%02d:%02d", ans/60, ans%60);
    return string(tmp, l);
}