[C++] 2018 카카오 블라인드 셔틀버스

문제 설명

---

셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

ntmtimetableanswer

1	1	5	["08:00", "08:01", "08:02", "08:03"]	"09:00"
2	10	2	["09:10", "09:09", "08:00"]	"09:09"
2	1	2	["09:00", "09:00", "09:00", "09:00"]	"08:59"
1	1	5	["00:01", "00:01", "00:01", "00:01", "00:01"]	"00:00"
1	1	1	["23:59"]	"09:00"
10	60	45	["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]	"18:00"

 

 

 

접근 방법

---

가장 마지막에 타기 위해서는 가장 마지막 버스를 타면 됩니다. 이 때 2가지 경우가 있습니다.

1. 마지막 버스에 빈자리가 있는 경우

2. 마지막 버스에 빈자리가 없는 경우

 

1번의 경우 마지막 버스의 출발시간이 정답이 될 것입니다.

2번의 경우는 마지막 버스에 마지막으로 올라탄 사람보다 1분 일찍 도착한다면 마지막 버스를 탈 수 있게 될 것입니다.

 

문제 풀이

 

1. 위의 결과를 도출하기 위해 [버스에 타고있는 인원, 버스의 출발시간, 버스에 마지막으로 탄 사람의 도착시간] 3가지의 정보가 필요합니다. 이 3가지의 정보를 담고 있는 구조체를 가진 배열을 초기화 합니다.

2. 또한 timetable이 string의 형식이므로 계산을 편히 하기 위해 int로 바꾸어줄 필요가 있습니다. int형으로 바꾸어 주었다면 사람들을 도착한 순서대로 정렬을 시킵니다.  

typedef struct info{
    int cnt, start, last;
};

vector<int> table; //timetable을 int로 변환
vector<info> busTable; //버스 배열

void init(vector<string> &timetable, int n, int t, int m){
    
    //time table을 int로 변환하여 table에 입력
    for(int i=0;i<timetable.size();i++){
        string t = timetable[i];
        int h = atoi(t.substr(0,2).c_str()); 
        int m = atoi(t.substr(3,2).c_str()); 
        table.push_back(h*60 + m);
    }
    //도착한 순서대로 정렬(오름차순)
    sort(table.begin(), table.end());
    
    //버스의 정보를 담고 있는 배열 초기화
    int start = 9*60; //출발시간이 09:00이므로
    for(int i=0;i<n;i++){ //버스는 n번 운행 됨
        busTable.push_back({0, start, 0}); //탑승한 인원, 출발시간, 마지막에 탑승한 사람의 도착시간 
        start += t; //t분 간격으로 운행
    }
}

 

이러한 초기화 과정의 끝났다면 모든 승객을 버스에 배치 시켜 봅니다.

 

 사람의 도착시간이 버스의 출발시간 보다 빠르고 버스에 빈 자리가 있을 때에만 버스에 탑승이 가능합니다.

반대의 경우는 탑승 불가능 하며 다음 버스에 배치를 해야합니다.

string solve(int m, int n){
    
    int busNum = 0;
    string ans = "";
    
    for(int i=0;i<table.size();i++){
        //버스에 탈 수 있는 경우, 수용가능하며 시간이 맞을 때
        if(busTable[busNum].cnt < m && table[i] <= busTable[busNum].start){
            busTable[busNum].cnt++;
            busTable[busNum].last = table[i];
        } // 시간이 밀리거나 버스가 꽉 찾다면
        else{
            busNum++; //다음 버스
            i--;  //현재 인원이 아직 처리가 안됬기 때문임
        }
        
        //모든 버스가 운행 종료
        if(busNum >= n)
            break;
    }
    
    //마지막 버스
    info bus = busTable.back();
    //버스에 빈 자리가 있다면 버스의 출발시간, 아니라면 버스에 탑승한 마지막 인원 보다 1분 일찍
    return ans = (bus.cnt < m) ? intToStr(bus.start) : intToStr(bus.last - 1);
}

 

 

소스 코드

---

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

using namespace std;

typedef struct info{
    int cnt, start, last;
};

vector<int> table;
vector<info> busTable;

void init(vector<string> &timetable, int n, int t, int m){
    
    for(int i=0;i<timetable.size();i++){
        string t = timetable[i];
        int h = atoi(t.substr(0,2).c_str());
        int m = atoi(t.substr(3,2).c_str());
        table.push_back(h*60 + m);
    }
    sort(table.begin(), table.end());
    
    int start = 9*60;
    for(int i=0;i<n;i++){
        busTable.push_back({0, start, 0});
        start += t;
    }
}

string intToStr(int time){
    
    int h = time/60;
    int m = time%60;
    
    string H = to_string(h);
    string M = to_string(m);
    
    H = (H.size() == 1) ? "0" + H : H;
    M = (M.size() == 1) ? "0" + M : M;
    
    return H + ":" + M;
}

string solve(int m, int n){
    
    int busNum = 0;
    string ans = "";
    
    for(int i=0;i<table.size();i++){
        //버스에 탈 수 있는 경우, 수용가능하며 시간이 맞을 때
        if(busTable[busNum].cnt < m && table[i] <= busTable[busNum].start){
            busTable[busNum].cnt++;
            busTable[busNum].last = table[i];
        } // 시간이 밀리거나 버스가 꽉 찾다면
        else{
            busNum++;
            i--;
        }
        
        if(busNum >= n)
            break;
    }
    
    info bus = busTable.back();
    return ans = (bus.cnt < m) ? intToStr(bus.start) : intToStr(bus.last - 1);
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    init(timetable,n,t,m);
    
    return answer = solve(m, n);
}