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

✅ LV.3

📌 2018 KAKAO BLIND RECRUITMENT

✏️ 최종 솔루션

1. 대기시간을 분 단위로 전환해서 오름차순 우선순위 큐에 저장
2. 버스 탑승 가능 시간을 돌면서 현재 시간에 탈 수 있는 대기시간이 있으면 버스 정원만큼 pop 하고 현재까지 마지막으로 탄 사람의 대기시각 저장하고 현재 버스에 탄 정원을 새로운 버스를 탈 때마다 갱신해서 마지막 버스에 탄 정원과 마지막 버스에 마지막으로 탄 사람의 대기시각 저장
3. 모든 탐색 후에 마지막 버스에 탄 정원과 버스에 탈 수 있는 정원이 같으면 마지막 버스에 마지막으로 탄 사람의 대기시각보다 1분 빠른 시각을 return
   이외의 경우는 막차에 탈 수 있다는 것이기 때문에 막차시간 return
4. 최종 answer 을 string 형태로 변환

📌 self feedback

버스에 제일 늦게 탄 사람의 시간을 저장해서 아무것도 저장되지 않으면 아무도 탈 수 없는 것이기 때문에 막차시간을 return하고 나머지는 막차나 마지막 버스를 마지막으로 탄 사람의 시간 -1 한 시간을 return 해야한다고 생각했지만 이 발상은 예외처리가 너무 복잡해짐

막차가 꽉 찼는지의 여부를 판단하는 것이 관건이었음

✏️ 최종 code

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    
    priority_queue<int,vector<int>,greater<>> pq;
    for(int i=0;i<timetable.size();i++) {
        string s=timetable[i];
        int cnt=stoi(s.substr(0,2))*60+stoi(s.substr(3));
        pq.push(cnt);
    }
    
    // 막차에 마지막으로 탑승하는 숫자 구하기
    int arrived=9*60;
    int last=-1;
    int cnt=0;
    for(int i=0;i<n;i++) {
        if(i>0 )arrived+=t;

        if(arrived>=24*60) break;
        
        cnt=0;
        while(!pq.empty()) {
            if(cnt==m) break;
            
            int tp=pq.top();
            if(tp<=arrived) {
                pq.pop();
                cnt++;
                last=tp;
            }
            else break;
        }
    }
    
    int tme;

    if(cnt==m) tme=last-1;
    else tme=tme=(n-1)*t+540;
        
    string h="";
    string mm="";
    
    if(tme/60>=10) h=to_string(tme/60);
    else if(tme/60==0) h="00";
    else h="0"+to_string(tme/60);
    
    if(tme%60>=10) mm=to_string(tme%60);
    else if(tme%60==0) mm="00";
    else mm="0"+to_string(tme%60);
    
    answer=h+":"+mm;
    
    return answer;
}