셔틀 버스
Description
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.
Input
입력 형식
셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.
- 0 ＜ n ≦ 10
- 0 ＜ t ≦ 60
- 0 ＜ m ≦ 45
- timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
- 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.
Output
출력 형식
콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.
Example
Code
#include <bits/stdc++.h>
using namespace std;
int change_num(string time){
int number = 0;
number = stoi(time.substr(0,2))*60 + stoi(time.substr(3,2));
return number;
}
string change_time(int time){
int h = time / 60;
int m = time % 60;
string str = "";
if (h < 10){
str += '0';
}
str += to_string(h) + ':';
if( m < 10)
str += '0';
str += to_string(m);
return str;
}
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
int cone_time = 0;
map<int, vector<int> > bus_time;
int crew_number = timetable.size();
vector<int> bus_time_vector (n);
// Set Bus Time Table
int start_time = 540; // 09:00
for(int i=0; i<n; i++){
bus_time[start_time + i*t] = {};
bus_time_vector[i] = start_time + i*t;
}
vector<int> num_timetable = {};
for(int i=0; i<crew_number; i++){
int crew_time = change_num(timetable[i]);
num_timetable.push_back(crew_time);
}
sort(num_timetable.begin(), num_timetable.end());
queue<int> q_num_timetable;
for(int t : num_timetable){
q_num_timetable.push(t);
}
for(int i=0; i<n; i++){
int cnt=1; // cannot be bigger than m
int bus_arrive = bus_time_vector[i];
while(cnt <= m && !q_num_timetable.empty() && q_num_timetable.front() <= bus_arrive){
int q_front = q_num_timetable.front();
bus_time[bus_arrive].push_back(q_front);
q_num_timetable.pop();
cnt++;
}
}
// 마지막 차 만차로 출발하는 지 확인
if(bus_time[bus_time_vector[n-1]].size() == m){// 만차로 출발
map<int, int> last_bus_group;
for(int time : bus_time[bus_time_vector[n-1]]){
if(!last_bus_group[time])
last_bus_group[time] = 1;
else
last_bus_group[time] ++;
}
int people = 0;
for(auto time_x : last_bus_group){
people += time_x.second;
if(people >= m)
cone_time = time_x.first-1;
}
}
else{ // 자리 있음
cone_time = bus_time_vector[n-1];
}
answer = change_time(cone_time);
return answer;
}Thoughts
위 문제는 2017 카카오 신입 공채 1차 코딩테스트 4번째 문제로 정답률이 30% 미만이였던 어려운 편에 속한 문제이다.
개인적인 난이도는 중 정도라고 생각하는데, 이 문제에서 가장큰 핵심은 바로 문제의 이해도이다.
나 역시 문제를 제대로 이해하는 것에 꽤 많은 시간을 할애 했고 한 번에 올바른 방향으로 문제풀이를 설계했기 때문에 목표 시간이였던 1시간 내에 풀 수 있었으나, 어렵게 접근했다면 꽤 오래 걸렸을 것이다.
우선 크루들이 역에 도착하는 시간들이 String으로 주어지는데, 이 시간 정보를 어떤식으로 가지고 있으면 좋을지, 또 주어진 n과 t로 부터 역에 도착하는 버스들의 정보를 어떤식으로 구현해 놓을지 생각을 많이 해야 했다.
시간 정보는 모두 int로 시간x60 + 분 관계로 부터 모든 시간을 정수형 단위로 통일하기로 했고, 주어진 n,t로 부터 버스의 출발 시간을 만들었다.
그 다음 부터 나의 풀이의 접근법은 다음과 같다.
1. 모든 버스 시간표를 만든다.
2. 모든 크루들의 도착 시간을 Queue에 담는다.(시간 순서대로)
3. 첫 버스 시간 부터, 차에 최대로 탈수 있는 인원인 m만큼 가능한 사람을 Queue의 front에서 한 명씩 제거한다.
4. 완성된 모든 버스시간표 마다의 가능인원이 담긴 Hash map에서 마지막 차가 어떻게 출발 했는지 체크한다.
- 1) 마지막차가 만원으로 출발하는 경우
- 2) 마지막차가 만원이 아닌 경우
4-1 경우 처럼 마지막 차가 만원으로 출발 하는 경우는 콘이 빨리 가지 않으면 아예 사무실을 못간다. 따라서 마지막 차를 타고 가는 크루들의 시간들을 조사하여 1등 시간대로 도착한 그룹과 같은 시간에 도착하면 되는지 파악해서 1등 그룹이랑 같은 시간대에 도착해도 버스를 탈 수 있으면 그시간, 탈 수 없다면 1등 그룹보다 1분 먼저 도착해야 한다.
4-2의 경우처럼 마지막차가 만원이 아니라면 마지막 버스의 도착시간에 맞춰 콘이 도착하면 된다.
위와 같은 알고리즘으로 풀면 쉽게 답을 구할 수 있다.
