[2017 카카오 코딩테스트] 셔틀 버스

분류 

시뮬레이션

요구사항

1. 크루의 도착 시간 분으로 변환하기

2. 마지막 버스까지 사람 태우기

3. 마지막 버스에서 한 사람 자리 비우고 다 태우기

4. 마지막 사람(정답) 처리하기

풀이

1. 크루의 도착 시간 분으로 변환하기

-> 정해진 문자열이 주어지므로, 시간을 분으로 전환해서 도착시간을 구한다. 구하고 나서 우선순위 큐에 넣는다

2. 마지막 버스이전까지 버스에 사람 태우기

-> 마지막 버스 이전까지 버스 도착 시간 이전에 온 사람들을 태운다

3. 마지막 버스에서 한 사람 자리 비우고 다 태우기

-> 마지막 버스에서 마지막 한자리 빼고 사람을 다 태운다.

4. 마지막 사람(정답) 처리하기

-> 마지막 사람은 버스의 도착 시간이거나, 마지막 한자리보다 1분 빨리온 시간이다

아래 블로그를 참조하였다.

https://kswims.tistory.com/163

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>
#include <map>
#include <string>
#include <vector>

using namespace std;

int Arrive_time[1500]={0,};

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    //  [08:00, 08:01, 08:02, 08:03]
    priority_queue<int,vector<int>, greater<int> > q;
    //도착한 사람 시간 count해준다
    for(int i=0 ; i <timetable.size(); i++){
        int H_time = stoi(timetable[i].substr(0,2));
        int M_time = stoi(timetable[i].substr(3,5));
        int Now_time = H_time*60 + M_time;
        cout<<Now_time<<endl;
        q.push(Now_time);
    }
    //마지막 버스가 될 때까지 확인한다
    for(int i=0 ; i <n-1 ; i++){
        int Now_people_cnt=0;
        int Now_bus_start_time= 540 + t*i;
        while(!q.empty() && Now_people_cnt<m){
            if(q.top() > Now_bus_start_time)
                break;
            else{
                q.pop();
                Now_people_cnt++;
            }
        }
    }
    //마지막처리
    int Last_bus_start_time=540 + t*(n-1);
    int Last_people_cnt=0;
    while(!q.empty() && Last_people_cnt<m-1){
            if(q.top() > Last_bus_start_time)
                break;
            else{
                q.pop();
                Last_people_cnt++;
            }
    }

    //더 태울사람이 있다?
    int ans=0;
    if(q.empty() || q.top() > Last_bus_start_time){
        ans=Last_bus_start_time;
    }
    else{
        ans=q.top()-1;
    }


    int H = ans/60;
    int M = ans%60;
    answer += H/10 + '0';     
    answer += H%10 + '0';
    answer += ':';
    answer += M/10 + '0';      
    answer += M%10 + '0';

    
    cout<<answer<<endl;
    return answer;
}
int main(){
    int n, t, m;
    vector<string> timetable;
    n=1;
    t=1;
    m=5;
    timetable.push_back("08:00");
    timetable.push_back("08:01");
    timetable.push_back("08:02");
    timetable.push_back("08:03");
    solution(1,1,5,timetable);

}