"2018 KAKAO BLIND RECRUITMENT" > [1차] 셔틀버스

문제: programmers.co.kr/learn/courses/30/lessons/17678

 

<조건>

• 셔틀은 항상 09:00에 운행 시작
• 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다.
  • ex) 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
  • ex) m이 4일 때, 9시 이전에 도착한 사람이 5명이라면, 가장 마지막에 온 사람은 다음 셔틀을 타야 한다.
• 콘은 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다.

 

 

문제 풀이:

1. 먼저, timetable 값들을 정수(분 단위)로 변환시켜 timeV라는 vector에 저장했다.
   • ex) "09:01" -> 9*60+1=541
   • [string -> int]로 변환하려면 stoi()함수를 사용하면 된다.
2. 크루가 대기열에 도착한 시각들(timetable)은 정렬되지 않은 형태로 들어오므로 timeV를 정렬한다.
3. timetable에 있는 사람들이 셔틀버스를 어떻게 탔는지 기록한다.
   • 이를 위해, 먼저 vector<pair<int,int>> bus 변수를 생성하였다.
   • first: 해당 버스(x번 째 버스)에 탄 사람 수
   • second: 해당 버스에 탄 사람 중 대기열에 가장 마지막에 도착한 사람의 도착 시간
   • 먼저 대기열에 도착한 사람부터 while문을 돌며 한 명씩 버스에 태운다 (bus 변수에 push한다)
     • busN: 현재 버스 번호(몇 번째로 오는 셔틀버스인가) -> 0~(n-1)
     • p: timetable에 존재하는 사람 번호 -> 도착 순서대로 0~(timetable.size()-1)
     • busN번 버스 이전에 온 사람은 해당 버스에 탑승한다. 
       • 하지만, 해당 버스가 이미 만원이라면(bus[busN].first>=m) 다음 버스에 타야 하므로 busN++;
       • 현재 버스 or 다음 버스에 현재 사람(p)이 탑승 -> bus[busN].first++;
       • 해당 버스에 탄 사람 중 대기열에 가장 마지막에 도착한 사람의 도착 시간을 갱신
       • 다음 사람 태우기 위해 p++;
     • busN번 버스 이후에 온 사람이면 다음 버스를 타야 하므로 busN++;
4. "이제 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각"을 구해야 한다.
   
   1. 사무실에 최대한 늦게 가려면, 마지막 셔틀버스를 타야 한다.
   2. 즉, 두 가지 경우만 생각하면 된다.
   3. 마지막 셔틀버스에 여석이 있는 경우
      1. 해당 셔틀 버스 도착 시간에 딱 맞춰오면 된다.
   4. 마지막 셔틀버스가 꽉 찬 경우
      1. 해당 버스 탑승객 중 가장 마지막에 대기열에 온 사람의 도착 시간보다 1분 더 일찍 오면 된다.
         1. 1분 단위이고, 콘은 동시에 도착하면 맨 뒤이기 때문

 

 

 

소스 코드:

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> timeV;
vector<pair<int,int>> bus;
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    bus.resize(62);
    
    for(string crew: timetable){
        int hour = stoi(crew.substr(0,2));
        int min = stoi(crew.substr(3,2));
        
        timeV.push_back(hour*60+min);
    }
    sort(timeV.begin(), timeV.end());
    
    int p=0,busN=0;

    while(p<timeV.size()&&busN<n){
        if(timeV[p]<=540+t*busN){
            if(bus[busN].first>=m) busN++;
            bus[busN].second = max(bus[busN].second, timeV[p]);
            bus[busN].first++;
            p++;
        }
        else{
            busN++;
        }
    }
    
    int corn=60*9;
    if(bus[n-1].first<m){
        corn = 540+t*(n-1);
    }
    else{
        corn = bus[n-1].second-1;
    }
    
    int hour= corn/60;
    if(hour<10) answer ='0'+to_string(hour);
    else answer=to_string(hour);
    
    answer=answer+':';
    int min = corn%60;
    if(min<10) answer =answer+'0'+to_string(min);
    else answer=answer+to_string(min);
    
    return answer;
}