프로그래머스 - [1차] 셔틀버스 (Lv.3)

문제 링크

• 👉 셔틀버스

문제 설명

• 9:00 부터 t 분 간격으로 n 회 운영하는 셔틀버스가 있다.
• 카카오 직원인 크루들은 00:01 부터 23:59 사이의 시간에 셔틀버스 정류장에 도착한다.
• 직원 중 한명인 콘은 사무실에 가장 늦게 도착하는 시간으로 셔틀버스를 이용하려고 한다.
• 콘은 같은 시간에 셔틀버스 정류장에 도착해도 다른 크루들의 맨 뒤에 선다.
• 콘이 정류장에 도착해야 하는 가장 늦은 시간을 구하라.

문제 접근

• 문제 풀이의 핵심은 콘은 최대한 마지막 셔틀 버스를 타야한다는 점이다.
• 즉, 중요한 점은 마지막 버스에 자리가 있느냐 없느냐를 판단해야 한다.
  • 자리가 있다면 마지막 버스가 출발하는 시간에 맞춰서 정류장에 도착하면 된다.
  • 자리가 없다면 가장 마지막에 버스를 탔던 크루의 시간보다 1분 일찍 도착하면 된다.
    • 위 로직이 성립하는 이유는 같은 시간에 도착한 크루가 여러 명이 있더라도 1분이라도 그들보다 앞선다면, 마지막 혹은 이전의 셔틀버스를 탈 수 있기 때문이다.

구현(All Pass)

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    vector<int> crewTable;
    string answer = "";
    stringstream stm;
    int hh, mm;
    for(int i=0; i<timetable.size(); i++){
        stm.clear();
        stm.str(timetable[i]);
        stm >> hh; stm.get(); stm>>mm;
        int time = hh*60 + mm;
        crewTable.push_back(time);
    }
    sort(crewTable.begin(), crewTable.end());
    int busTime = 540;
    int idx=0, cnt=0, time = 0;
    for(int i=0; i<n; i++){
        cnt=0;
        for(int j=idx; j<crewTable.size(); j++){
            if(crewTable[j] > busTime) break;
            cnt++; idx++;
            if(cnt == m) break;
        }
        // 마지막 버스에 몇명이 탔는지만 중요!
        if(i==n-1){
            if(cnt == m)
                time = crewTable[idx-1]-1;
            else
                time = busTime;
        }
        busTime += t;
    }
    
    hh = time/60;
    mm = time%60;
    if(hh<10) answer += "0";
    answer += to_string(hh) + ":";
    if(mm<10) answer += "0";
    answer += to_string(mm);
    
    return answer;
}