프로그래머스: [1차] 셔틀버스⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
난이도 ⭐⭐⭐
유형 : 구현
🧐 문제
문제 설명
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 ‘크루’라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
- 셔틀은
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 사이의 값이 될 수 있다.
입출력 예제
| n | t | m | timetable | answer |
|---|---|---|---|---|
| 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” |
✏️ 나의 풀이
#include <bits/stdc++.h>
using namespace std;
// 버스가 언제 도착하는지가 담긴 테이블(오름차순)
vector<int> simple_bustable;
// 사람들이 언제 도착하는지가 담긴 테이블(오름차순)
vector<int> simple_timetable;
// key: 버스 도착 시간
// value: 사람 도착 시간
// 어떤 버스에 어떤 사람들이 탑승하는지 저장해두기 위한 변수(내림차순)
map<int, vector<int>, greater<int>> taken;
// 초기화 작업
void init(int n, int t, vector<string>& timetable) {
// 사람 도착 시간을 간단한 정수 형태로 저장
// ex) 09:10 -> 550
for(string time : timetable) {
int ind = time.find(':');
int h = stoi(time.substr(0, ind));
int m = stoi(time.substr(ind+1, time.size()));
simple_timetable.push_back(h*60 + m);
}
// 오름차순 정렬
sort(simple_timetable.begin(), simple_timetable.end());
// 버스 도착 시간을 간단한 정수 형태로 저장
for(int i=0; i<n; i++) {
taken.insert({9*60 + t*i, vector<int>()});
simple_bustable.push_back(9*60 + t*i);
}
}
// 0으로 채운다.
// ex) 9 -> 09, 10 -> 10
string formatting(string input) {
if(input.length() != 2) {
input.insert(0, "0");
}
return input;
}
// 정수 형태 시간을 "시간:분" 형태로 변환시킨다.
// ex) 550 -> 09:10
string int2str_time(int st) {
return formatting(to_string(st/60)) + ':' + formatting(to_string(st%60));
}
string solution(int n, int t, int m, vector<string> timetable) {
// 타임, 버스 테이블 초기화
init(n, t, timetable);
int tt_ind = 0;
// 각 버스들에 태울수 있는 만큼 태운다.
for(int sb : simple_bustable) {
if(simple_timetable.size() == tt_ind) break;
for(int i=0; i<m; i++) {
if(simple_timetable.size() == tt_ind) break;
// 사람 도착 시간 <= 버스 도착 시간
// 해당 시간대의 버스를 탈수 있는지 체크한다.
if(simple_timetable[tt_ind] <= sb) {
taken[sb].push_back(simple_timetable[tt_ind]);
tt_ind++;
}
}
}
// taken은 내림차순으로 된 맵이므로, 가장 늦은 시간대의 버스를 가져온다.
// 해당 버스에 자리가 있다면, 그 시간대의 버스를 반환
// 해당 버스에 자리가 없다면, m번째 사람보다 1분 더 빨리오면 된다.
auto it = taken.begin();
if(it->second.size() < m) return int2str_time(it->first);
else return int2str_time(it->second[m-1]-1);
}
✔️ 다른 사람의 풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string solution(int n, int t, int m, vector<string> timetable)
{
vector<int> Crew;
for (int i = 0; i < timetable.size(); i++)
{
string S_Hour = "";
S_Hour = S_Hour + timetable[i][0];
S_Hour = S_Hour + timetable[i][1];
int Hour = stoi(S_Hour);
string S_Minute = "";
S_Minute = S_Minute + timetable[i][3];
S_Minute = S_Minute + timetable[i][4];
int Minute = stoi(S_Minute);
int Time = Hour * 60 + Minute;
Crew.push_back(Time);
}
sort(Crew.begin(), Crew.end());
int Shuttle_Time = 540;
int Crew_Idx = 0;
int Answer_Time;
for (int i = 1; i <= n; i++, Shuttle_Time = Shuttle_Time + t)
{
int Cnt = 0;
for (int j = Crew_Idx; j < Crew.size(); j++)
{
if (Crew[j] <= Shuttle_Time)
{
Crew_Idx++;
Cnt++;
if (Cnt == m) break;
}
}
if (i == n)
{
if (Cnt == m) Answer_Time = Crew[Crew_Idx - 1] - 1;
else Answer_Time = Shuttle_Time;
}
}
string answer = "";
int Hour = Answer_Time / 60;
int Minute = Answer_Time % 60;
char A = Hour / 10 + '0';
char B = Hour % 10 + '0';
char C = Minute / 10 + '0';
char D = Minute % 10 + '0';
answer = answer + A;
answer = answer + B;
answer = answer + ':';
answer = answer + C;
answer = answer + D;
return answer;
}
// 출처: https://yabmoons.tistory.com/637 [얍문's Coding World..:티스토리]
🧐 분석
나의 코드와 같은 방식으로 풀이하고 있다.
차이점은, 각 셔틀버스에 사람들을 태우는 taken이라는 변수를
따로 사용하고 있다는 점이 있다.
시간 복잡도와 공간 복잡도를 생각했을 때, 얍문님의 코드가 더 좋아보인다.
나의 코드는 함수를 분리한 것은 좋았지만,
더 좋은 변수와 함수 이름을 사용해야 한다.
댓글남기기