[그리디] 셔틀버스 - 2018 KAKAO BLIND RECRUITMENT

해결 방법

이 문제의 핵심은 막차의 만원 여부이다.

i) n, t를 이용하여 버스의 timetable을 만든다.

ii) 크루의 timetable을 정렬한다.

iii) 버스의 timetable과 크루의 timetable을 차례대로 비교해가며 탑승할 수 있는 크루를 먼저 온 순서대로 태운다. 단, 막차는 몇 명이 타는지 카운트해야 한다.

iv) 막차가 만원이 아니라면, 즉, 카운트한 값이 m과 다르다면 콘은 그대로 막차를 타고가면 된다.

v) 막차가 만원이라면, 즉, 카운트한 값이 m과 일치하다면 콘은 막차에서 가장 늦게 탄(우선순위가 가장 낮은)사람의 도착시간보다 1초 일찍 오면 된다.

 

 

소스 코드

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

string time_converter(int t){ // 정수 형태의 시간을 "HH:MM" 형태로 변환
    string time="";
    string sm=to_string(t/60);
    string sh=to_string(t%60);
    if(sm.length()==1) time+="0";
    time+=sm+":";
    if(sh.length()==1) time+="0";
    time+=sh;
    return time;
}

vector<string> bus_timetable(int n, int t){ // 셔틀 버스 timetable 생성
    vector<string> bt;
    int start=540; //9시 정각(9*60)
    bt.push_back(time_converter(start));
    for(int i=1;i<n;i++){
        start+=t;
        string time=time_converter(start);
        bt.push_back(time);
    }
    return bt;
}

string solution(int n, int t, int m, vector<string> timetable) {
    vector<string> bt = bus_timetable(n, t);
    string answer=bt.back(); //기본값은 막차로 지정
    int p=0; //timetable 검사 위치
    int lastcnt=0; //막차 탑승 인원 수
    sort(timetable.begin(), timetable.end());    
    for(int i=0;i<bt.size();i++){
        int cnt=m; // 한 셔틀에 탈 수 있는 최대 크루 수
        while(cnt!=0&&p<timetable.size()){
            if(timetable[p].compare(bt[i])<=0){
                p++;
                cnt--;
                if(i==bt.size()-1) lastcnt++;
            }
            else break;
        }
    }
    if(lastcnt!=m) return answer; // 막차가 만원이 아닐 경우 막차에 그대로 탑승
    string lastpt = timetable[p-1]; // 막차에서 우선순위가 가장 낮은 사람의 도착시간
    int mytime=stoi(lastpt.substr(0, 2))*60+stoi(lastpt.substr(3, 2))-1;
    return time_converter(mytime);
}

 

테스트케이스 24개 모두 정답