[C++로 풀이] 셔틀버스⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 셔틀버스
난이도 ⭐⭐⭐
🚀 문제
🔥 문제 설명
- 첫 버스는 무조건 09 : 00 에 온다.
- 같은 시간에 온 사람들이 선 줄에서 콘은 언제나 맨 뒤에 줄선다.
- 버스 오는 시간에 줄 선 사람도 버스에 탈 수 있다.
콘은 게으르기 때문에 마지막 버스 타고 출근할 수 있는, 최대한 늦게 줄을 서는 시간의 그 마지노선를 구하는 문제이다.
n은 버스의 수, t는 간격, m은 버스에 탑승할 수 있는 최대 인원.
- 입출력 예제 1 👉
09:00- 버스는 딱 1번 온다. 즉 09:00 버스 하나 밖에 없다. 이미 09:00 전에 4 명이 줄서있는데 버스는 최대 5명까지 태울 수 있으므로 콘은 무난하게 09:00 에 와도 된다.
- 입출력 예제 2 👉
09:09- 버스는 10분 간격으로 2 번 오기 때문에 09:00, 09:10 이렇게 온다. 콘은 09:10 버스를 타야한다. 08:00 에 줄 선 크루는 09:00 버스를 타고 출근할테고, 09:09, 09:10 에 줄 선 크루들이 09:10 버스를 탈 것이다. 버스의 정원은 2 명이기 때문에 09:10 에 줄을 선 크루보다 콘이 더 일찍 와야한다는 소리이다. 콘은 항상 같은 시간에 온 사람들보다 맨 뒤에 오기 때문에 09:09 에 와도 09:09 인 사람이 딱 2명이 되는거라 버스 정원을 초과하지 않는다. 즉, 콘은 09:09 에 와야 09:10 마지막 버스를 탈 수 있다. (09:10 에 줄서는 크루는 버스 못 타겠지..☆)
- 입출력 예제 3 👉
08:59- 버스의 정원은 2 명이며, 09:00, 09:01 이렇게 2 번 온다. 이미 09:00 에 줄 서 있는 사람만 4명이기 때문에 이 사람들이 2 명씩 09:00, 09:01 버스에 나눠타게 된다. 콘은 같은 시간에 온 사람들 중에서 가장 뒤에 줄을 서기 때문에 09:00 에 오면 콘은 두 버스 모두에 타지 못한다.(5번째가 되서) 따라서 콘은 08:59 에 줄을 서야 버스를 탈 수 있게 된다.
- 입출력 예제 4 👉
00:00- 예제 3 처럼 00:01 에 온 5 명이 전부 5명 정원인 버스를 딱 한번 09:00에 오는 버스에 모두 타버릴 것이기 때문에 콘은 00:01 보다 더 일찍 와야 한다. 00:01에 줄을 서면 콘은 00:01 에 온 사람들 중 6번째가 되기 때문에 못 탄다. 그러므로 콘은 00:00 에 줄을 서야 한다.
- 입출력 예제 5 👉
09:00- 버스는 09:00 에 딱 한번 오며 한 명만 태울 수 있다. 줄 서는 크루가 23:59 에 한명 뿐이니 콘은 편하게 09:00 에만 오면 된다.
- 입출력 예제 6 👉
18:00- 버스가 1시간 단위로 09:00, 10:00, .. ,18:00 에 10 번 오게 된다. 줄 선 사람이 모두 23:59 라서 콘은 그냥 18:00 에만 오면 마지막 버스 탈 수 있다.
처음에 이해를 잘 못 했던 문제이다.😭 그러나 문제만 잘 이해하고나면 어렵지 않게 풀이할 수 있는 문제였다.
🚀 내 풀이
🔥 2 차 풀이 ⭕
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
int result = 0;
sort(timetable.begin(), timetable.end());
vector<int> timeTable;
for (auto& time : timetable)
timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));
int index = 0;
int busTime = 540; // 09:00
for (int count = 1; count <= n; ++count) {
int numOfGetOn = 0;
while (numOfGetOn < m && index < timeTable.size()) {
if (timeTable[index] <= busTime) {
numOfGetOn++;
index++;
}
else break;
}
if (count == n) {
if (numOfGetOn < m)
result = busTime;
else
result = timeTable[index - 1] - 1;
}
busTime += t;
}
int hours = result / 60;
if (hours <= 9)
answer = "0" + to_string(hours) + ":";
else
answer = to_string(hours) + ":";
int minutes = result % 60;
if (minutes <= 9)
answer += "0" + to_string(minutes);
else
answer += to_string(minutes);
return answer;
}
버스가 여유 있는지 여부를 따져야 한다.
- 크루들이 모든 버스에 다 탑승하더라도 콘이 그 뒤에 탈 수 있는 여유가 있다면
- 👉 여유가 있으니 그냥 마지막 버스시간에만 탑승하면 된다. 따라서 마지막 버스 시간에 줄서면 됨.
- 크루들이 모든 버스에 다 탑승하고나면 콘이 탈 수 있는 여유가 없다면
- 👉 콘은 마지막에 탈 수 있는 크루의 바로 앞에 줄 서야 마지막으로 겨우 탈 수 있다. 즉, 마지막으로 탈 수 있는 크루보다 "1 분" 앞서 줄서면 된다.
- 예를 들어 버스가
09:00,09:03이렇게 2 번 오고 3 명의 정원을 가진다면, [“09:00”, “09:01”, “09:01”, “09:03”, “09:03”] 일 때, 콘은 09:03 에 줄 선 크루보다 더 앞서야지만 버스를 탈 수 있다. 09:03 이 버스를 탈 수 있는 마지노선이기 때문이다. 그러나 콘은 같은 시간에서 맨 뒤에 줄을 서게 되므로 09:03 에 오면 콘은 09:03 에서도 꼴찌기 때문에 탈 수가 없다. 따라서 콘은 크루 대기열의 마지노선인 09:03 보다 1 분 먼저 09:02 에만 오면 된다.
- 예를 들어 버스가
- 👉 콘은 마지막에 탈 수 있는 크루의 바로 앞에 줄 서야 마지막으로 겨우 탈 수 있다. 즉, 마지막으로 탈 수 있는 크루보다 "1 분" 앞서 줄서면 된다.
1️⃣ 크루들이 줄서는 시간 비교하기 쉽게 분단위로 변환
vector<int> timeTable;
for (auto& time : timetable)
timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));
문제에서 주어진, 크루들이 줄서는 시간이 “HH:MM” 문자열 형태로 담겨잇는 timetable을 timeTable 벡터를 만들어서 이곳에 분 단위의 int 정수로 변환한다. ‘시’는 60 곱해주고 ‘분’은 그대로.
2️⃣ 버스에 크루들을 태운 후 버스가 여유있는지 없는지를 따져 콘이 줄서야 하는 시간 계산
int index = 0; // timeTable 의 인덱스 (크루 한명을 가리킴)
int busTime = 540; // '현재 버스'의 시간. 첫 버스는 무조건 "09:00" (540분)
for (int count = 1; count <= n; ++count) { // 버스는 n 번 온다.
int numOfGetOn = 0; // '현재 버스'에 탄 크루 인원 (m 을 넘어선 안된다.)
while (numOfGetOn < m && index < timeTable.size()) { // 버스에 태우는 작업
if (timeTable[index] <= busTime) { // 버스 도착시간 이하에 줄 섰다면 그 크루는 현재 버스에 탈 수 있다.
numOfGetOn++; // 탑승인원 + 1
index++; // 다음 크루 검사하러
}
else break; // 모든 크루 다 태웠거나 현재 버스 정원 다 찼으면 break.
}
// 모든 버스 다 검사 진행했다면 이제 버스가 여유로웠는지 아닌지 알 수 있다.
if (count == n) {
if (numOfGetOn < m) // 마지막 버스의 정원이 다 차지 못했다면 👉 버스 여유 있음
result = busTime; // 🤍콘은 마지막 버스 시간에만 오면 된다.
else if (numOfGetOn >= m) // 마지막 버스의 정원이 다 찼다면 👉 버스 여유 없다.
result = timeTable[index - 1] - 1; // 🤍콘은 마지막 버스에서 마지막으로 탑승한 사람을 밀어내고 그 사람보다 1분 앞서 타야 한다.
}
busTime += t; // 다음 버스 시간으로 업데이트 (다음 버스는 t 분 뒤에 온다.)
}
- while 문을 break 하고난 후의
index는 마지막으로 버스를 탄 크루가 줄 선 시간이다.- 버스에 여유가 없다면 콘은 이 크루를 제껴 맨 마지막으로 타기위해 1분만 앞서 타면 된다.
- 최종적으로
result에 “콘이 줄 서야 하는 마지노선 시간”이 담기게 된다.
3️⃣ 정답으로 구한 콘이 줄 서야 하는 마지노선 시간을 “HH:MM” 문자열로 변환
/* 시간 HH: */
int hours = result / 60;
if (hours <= 9) // 한 자리일 때
answer = "0" + to_string(hours) + ":";
else
answer = to_string(hours) + ":";
/* 분 MM */
int minutes = result % 60;
if (minutes <= 9) // 한 자리일때
answer += "0" + to_string(minutes);
else
answer += to_string(minutes);
return answer;
🔥 1 차 풀이 ⭕ (But 개선이 필요)
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
struct Bus {
int busTime;
vector<int> people;
};
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
vector<int> timeTable;
for (auto& time : timetable)
timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));
sort(timeTable.begin(), timeTable.end());
vector<Bus> bus;
int index = 0;
int busTime = 540; // 09:00
for (int count = 0; count < n; ++count) {
vector<int> getOn;
while (getOn.size() < m && index < timeTable.size()) {
if (timeTable[index] <= busTime) {
getOn.push_back(timeTable[index]);
index++;
}
else break;
}
bus.push_back({ busTime, getOn });
busTime += t;
}
int hours = 0, minutes = 0;
if (bus.back().people.size() < m) {
hours = bus.back().busTime / 60;
minutes = bus.back().busTime % 60;
}
else {
hours = (bus.back().people.back() - 1) / 60;
minutes = (bus.back().people.back() - 1) % 60;
}
if (hours <= 9)
answer = "0" + to_string(hours) + ":";
else
answer = to_string(hours) + ":";
if (minutes <= 9)
answer += "0" + to_string(minutes);
else
answer += to_string(minutes);
return answer;
}
처음에 제출했던 풀이이다. 근데 다 풀고나니 굳이 이렇게 풀 필요가 없겠네 싶었다. 버스에 여유가 없을 땐 마지막 버스에 탄 사람 중에서도 마지막으로 탈 수 있는 사람이 어떤 시간에 줄 섰는지 정보만 있으면 되는데(이 사람 바로 앞에 타면 되니까) 굳이 이렇게 Bus 구조체를 두어 모든 버스들마다 각각 vector로 해당 버스에 탈 수 있는 크루들 정보를 모두 저장할 필요가 전혀 없었다. 그래서 위의 2 차 풀이로, 버스에 다 탈 수 있는 여유가 없을 땐 마지막으로 탈 수 있는 크루의 바로 앞에 탈 수 있도록 고치고 다시 제출했었다.
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기