[프로그래머스 Lv3] : [1차] 셔틀버스

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17678

프로그래머스

셔틀버스 운행정보가 주어질 때, 콘이 셔틀을 타고 사무실로 갈 수 있는 가장 늦은 정류장 도착시간을 구하여라.

 

풀이

콘은 이미 다른 크루들이 몇시에 정류장에 도착하는 지 알고있다.

그리고 셔틀버스에는 정류장에 일찍 도착한 사람부터 탑승한다.

 

콘은 제일 늦게 정류장에 도착하고 싶어하기 때문에, 무조건 막차를 타야한다.

만약에 도착한 시간을 기준으로 크루들이 어떤 셔틀버스에 탈지 분배했을 때,

1. 막차가 만석이 아니라면, 콘은 막차 출발시간에 딱 맞춰 도착하면 된다.

2. 막차가 만석이라면, 콘은 m번째 사람보다 빨리 도착해야한다.

=> m번째 사람의 정류장 도착시간보다 1분 빠르게 도착한다.

 

코드 작성

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> crew; //크루들의 줄서는 시간
    for(auto Time : timetable){
        int clock = stoi(Time.substr(0,2));
        int minute = stoi(Time.substr(3,2));
        crew.push_back(clock * 100 + minute);
    }
    sort(crew.begin(), crew.end());
    vector<int> Bus; // 버스 시간표
    int clock = 9;
    int minute = 0;
    for(int i = 0; i<n; i++){
        Bus.push_back(clock * 100 + minute);
        minute += t;
        if(minute >= 60){
            minute %= 60;
            clock ++;
        }
    }
    vector<int> Board[11]; //i번 버스에 탑승할 크루 정보
    for(auto Crew : crew){
        int idx = lower_bound(Bus.begin(), Bus.end(), Crew) - Bus.begin();
        if(Board[idx].size() >= m){
            while(Board[idx].size() >= m && idx < Bus.size() - 1)
                idx++;
        }
        Board[idx].push_back(Crew);
    }
    int N_Bus = Bus.size();
    if(Board[N_Bus - 1].size() < m){
        if(Bus[N_Bus - 1]/ 100 < 10)
            answer += "0";
        answer += to_string(Bus[N_Bus - 1] / 100);
        answer += ":";
        if(Bus[N_Bus - 1] % 100 < 10)
            answer += "0";
        answer += to_string(Bus[N_Bus - 1] % 100);
    }
    else{
        int T = Board[N_Bus - 1][m-1];
        int C = T / 100;
        int M = T % 100;
        M--;
        if(M < 0){
            M = 59;
            C--;
        }
        if(C < 10)
            answer += "0";
        answer += to_string(C);
        answer += ":";
        if(M < 10)
            answer += "0";
        answer += to_string(M);
    }
    return answer;
}