알고리즘
99클럽 코테 스터디 16일차 TIL + 프로그래머스 셔틀버스 문제 풀이
개발공명
2025. 4. 22. 02:19
오늘의 문제
https://school.programmers.co.kr/learn/courses/30/lessons/17678
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 풀이
문제를 보고 생각한 것은 아래와 같다.
- 마지막 셔틀에 타는 것이 베스트
- 마지막 셔틀에 타는데
- m명 이상 대기 중이면 m번째 사람보다 1분 일찍 오면 됨
- m명 미만 대기 중이면 마지막 셔틀 도착 시간에 타면 됨
- 마지막 셔틀 -1 도착 시간 이전 사람은 버리면 됨
- but m이상이라 못 타고 남아 있는 사람 생각해야 함
- → 시간마다 확인하며 사람 줄여나가야 함
- 마지막 셔틀 도착 시간 이후 사람 버리면 됨
이런 생각을 가지고 문제를 풀기 시작했다.
우선 사람들 도착 시간을 풀기 쉽게 숫자화 해서 pair로 저장했다.
hour, minute 따로 벡터로 저장하려고 했는데 추후 정렬할 때 어지러워지니 pair로 했다.
vector<pair<int,int>> arrivalTime;
// 사람들 도착 시간 숫자화
for(int i=0;i<timetable.size();i++){
int hour = stoi(timetable[i].substr(0,2));
int minute = stoi(timetable[i].substr(3));
arrivalTime.push_back(make_pair(hour,minute));
}
그리고 버스들이 도착하는 시간들도 저장해 놨다.
여기서 중요한 것은 t번 버스가 오는데 첫번째 09:00시의 버스도 이 t번에 추가된다는 것이다.
그래서 우선 09:00는 저장하고 t-1번 다음 버스 시간을 저장했다.
// 첫번째 버스 도착 시간 추가
busArrivalTime.push_back(make_pair(9,0));
// 버스 도착 시간 숫자화
int nowHour = 9;
int sumMinute = 0;
for(int i=0;i<n-1;i++){
sumMinute+=t;
if(sumMinute>=60){
nowHour++;
sumMinute-=60;
}
busArrivalTime.push_back(make_pair(nowHour,sumMinute));
}
그 후 도착 시간이 정렬되지 않아서 정렬을 한다.
그리고 마지막 버스 전까지 사람들을 확인하며 타고 가는 사람들을 저장된 시간에서 제거한다.
마지막 버스 전까지이니 busArrivalTime.size()-1번 반복했다.
// 사람들 도착 시간 도착 순서대로 정렬
sort(arrivalTime.begin(),arrivalTime.end(),compare);
// 마지막 버스 전까지 사람들 태워서 보냄
for(int i=0;i<busArrivalTime.size()-1;i++){
int nowPeople=0;
int nowBusHour = busArrivalTime[i].first;
int nowBusMinute = busArrivalTime[i].second;
for(int j=0;j<arrivalTime.size();j++){
// 버스 꽉참
if(nowPeople==m){
break;
}
int personHour = arrivalTime[j].first;
int personMinute = arrivalTime[j].second;
// 아직 사람 도착 안 한 것, 버스 시간보다 사람 도착 시간이 늦은 경우
if(nowBusHour<personHour||(nowBusHour==personHour&&nowBusMinute<personMinute)){
break;
}
// 버스 탈 수 있는 사람 태움
if(nowBusHour>personHour||(nowBusHour==personHour&&nowBusMinute>=personMinute)){
nowPeople++;
arrivalTime.erase(arrivalTime.begin());
j--;
}
}
}
코드를 보면 위의 for문은 한 버스가 도착한 것이다.
아래의 for문은 사람들을 보며 태우는 것이다.
현재 버스의 사람을 체크하면서 사람 꽉 차면 아래 for문을 break해서 다음 버스 오도록 했다.
기다리는 사람들의 시간 중 가장 앞에 있는 사람의 시간을 확인한다. (정렬 했으니 제일 먼저온 사람)
이 사람이 버스에 타지 못하는 시간에 온 사람이라면 아래 for문 break해서 다음 버스 오도록 했다.
버스에 탈 수 있다면 버스에 탄 사람을 +1하고 그 사람을 기다리고 있는 사람 list에서 제거한 것이다.
이 if문 조건들이 중요했는데 처음에 아래와 같이 해서 애를 많이 먹었다.
아래 같이 하니까 문제를 풀다 여러 곳에서 문제가 터졌었다.
좀 더 조건 깔끔하게 할 수 있을 것 같은데 아직 모르겠다.
// 아직 사람 도착 안 한 것, 버스 시간보다 사람 도착 시간이 늦은 경우
if(nowBusHour<personHour||nowBusMinute<personMinute){
break;
}
// 버스 탈 수 있는 사람 태움
if(nowBusHour>=personHour&&nowBusMinute>=personMinute){
nowPeople++;
arrivalTime.erase(arrivalTime.begin());
j--;
}
이제 마지막 버스가 도착한 것이다.
남아있는 사람들의 list를 돌면서 m-1명까지 버스에 태우는 것이다.
그래서 nowPeople = 마지막 버스 탄 사람이 m-1인 경우 for문을 break 한다.
for문 안의 코드는 위와 같다.
제일 앞에 있는 사람의 시간을 보고 현재 시간 보다 늦으면 for문을 break한다.
그리고 시간이 현재 시간 이하이면 태우는 것이다.
// 마지막 버스 시간
int lastBusHour = busArrivalTime[busArrivalTime.size()-1].first;
int lastBusMinute = busArrivalTime[busArrivalTime.size()-1].second;
// 마지막 버스에 m-1명까지 태움
int nowPeople = 0;
for(int i=0;i<arrivalTime.size();i++){
if(nowPeople==m-1){
break;
}
int personHour = arrivalTime[i].first;
int personMinute = arrivalTime[i].second;
// 아직 사람 도착 안 한 것, 버스 시간보다 사람 도착 시간이 늦은 경우
if(lastBusHour<personHour||(lastBusHour==personHour&&lastBusMinute<personMinute)){
break;
}
// 버스 탈 수 있는 사람 태움
if(lastBusHour>personHour||(lastBusHour==personHour&&lastBusMinute>=personMinute)){
nowPeople++;
arrivalTime.erase(arrivalTime.begin());
i--;
}
}이제 나의 시간을 결정하는 시간이다.
나의 시간이 정해지는 경우의 수는 아래와 같다.
- 기다리는 사람이 있는 경우
- 기다리는 사람이 마지막 버스에 탈 수 있는 경우 = 이 사람보다 1분 일찍 와야 함
- 기다리는 사람이 마지막 버스에 탈 수 없는 경우 = 버스 도착 시간에 오면 됨
- 기다리는 사람이 없는 경우 = 버스 도착 시간에 오면 됨
그래서 arrivalTime.size()가 0인지 아닌지 if문으로 나뉜다.
기다리는 사람이 있는 경우 또 안에 if-else문이 있다.
1분 일찍와야 하는 경우에 기다리는 사람이 도착한 분이 0인지 아닌지 확인해야 한다.
왜냐하면 예를 들어 10:00에 도착한 사람보다 1분 일찍 오려면 09:59이 되어야 하기 때문에 무작정 1 빼면 안된다.
코드는 아래와 같다.
int myHour=0;
int myMinute=0;
// 기다리는 사람이 있는지 확인
// 기다리는 사람 있다면 = 그 사람이 마지막 버스에 탈 수 있는 사람인지 아닌지 확인
if(arrivalTime.size()!=0){
int lastPersonHour = arrivalTime[0].first;
int lastPersonMinute = arrivalTime[0].second;
// 기다리는 사람이 버스에 탈 수 있는 경우 -> 이 사람보다 1분 빨리 와야 함
if(lastBusHour>lastPersonHour||(lastBusHour==lastPersonHour&&lastBusMinute>=lastPersonMinute)){
if(lastPersonMinute==0){
myHour = lastPersonHour-1;
myMinute = 59;
}
else{
myHour = lastPersonHour;
myMinute = lastPersonMinute-1;
}
}
// 기다리는 사람이 버스에 탈 수 없는 경우 -> 버스 도착 시간에 오면 됨
else{
myHour = lastBusHour;
myMinute = lastBusMinute;
}
}
// 기다리는 사람 없다면 -> 버스 도착 시간에 오면 됨
else{
myHour = lastBusHour;
myMinute = lastBusMinute;
}
이제 시간을 문자화 해서 반환하면 끝이다.
// 시간 문자화
string myHourStr = "";
string myMinuteStr = "";
if(myHour<10){
myHourStr+="0";
}
myHourStr+=to_string(myHour);
if(myMinute<10){
myMinuteStr+="0";
}
myMinuteStr+=to_string(myMinute);
answer=myHourStr+":"+myMinuteStr;
return answer;
전체 코드
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
/*
셔틀 버스 규칙
1. 9시부터 n회 t분 간격으로 역에 도착
2. 하나의 셔틀에 최대 m명 승객 가능
3. 도착 순간에 도착한 사람까지 탈 수 있음
같은 시간에 도착한 크루 중 제일 뒤에 섬
셔틀 타고 갈 수 있는 도착 시간 중 제일 늦은 시간 구하기
생각
셔틀 횟수에 9시도 포함
마지막 셔틀에 타는 것이 베스트
마지막 셔틀에 타는데
m명 이상 대기 중이면 m번째 사람보다 1분 일찍오면 됨
m명 미만 대기 중이면 마지막 셔틀 도착 시간에 타면 됨
마지막 셔틀-1 도착 시간 이전 사람은 버리면 됨 (n이 몇인지 확인)
but m 이상이면 남아 있는 것 생각해야 함
-> 시간마다 확인하며 사람 줄여나가야 할 듯?
마지막 셔틀 도착 시간 이후 사람 버리면 됨
*/
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if(a.first==b.first){
if(a.second<b.second){
return a.second < b.second;
}
}
return a.first < b.first;
}
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
vector<pair<int,int>> arrivalTime;
vector<pair<int,int>> busArrivalTime;
// 사람들 도착 시간 숫자화
for(int i=0;i<timetable.size();i++){
int hour = stoi(timetable[i].substr(0,2));
int minute = stoi(timetable[i].substr(3));
arrivalTime.push_back(make_pair(hour,minute));
}
// 첫번째 버스 도착 시간 추가
busArrivalTime.push_back(make_pair(9,0));
// 버스 도착 시간 숫자화
int nowHour = 9;
int sumMinute = 0;
for(int i=0;i<n-1;i++){
sumMinute+=t;
if(sumMinute>=60){
nowHour++;
sumMinute-=60;
}
busArrivalTime.push_back(make_pair(nowHour,sumMinute));
}
// 사람들 도착 시간 도착 순서대로 정렬
sort(arrivalTime.begin(),arrivalTime.end(),compare);
// 마지막 버스 전까지 사람들 태워서 보냄
for(int i=0;i<busArrivalTime.size()-1;i++){
int nowPeople=0;
int nowBusHour = busArrivalTime[i].first;
int nowBusMinute = busArrivalTime[i].second;
for(int j=0;j<arrivalTime.size();j++){
// 버스 꽉참
if(nowPeople==m){
break;
}
int personHour = arrivalTime[j].first;
int personMinute = arrivalTime[j].second;
// 아직 사람 도착 안 한 것, 버스 시간보다 사람 도착 시간이 늦은 경우
if(nowBusHour<personHour||(nowBusHour==personHour&&nowBusMinute<personMinute)){
break;
}
// 버스 탈 수 있는 사람 태움
if(nowBusHour>personHour||(nowBusHour==personHour&&nowBusMinute>=personMinute)){
nowPeople++;
arrivalTime.erase(arrivalTime.begin());
j--;
}
}
}
// 마지막 버스 시간
int lastBusHour = busArrivalTime[busArrivalTime.size()-1].first;
int lastBusMinute = busArrivalTime[busArrivalTime.size()-1].second;
// 마지막 버스에 m-1명까지 태움
int nowPeople = 0;
for(int i=0;i<arrivalTime.size();i++){
if(nowPeople==m-1){
break;
}
int personHour = arrivalTime[i].first;
int personMinute = arrivalTime[i].second;
// 아직 사람 도착 안 한 것, 버스 시간보다 사람 도착 시간이 늦은 경우
if(lastBusHour<personHour||(lastBusHour==personHour&&lastBusMinute<personMinute)){
break;
}
// 버스 탈 수 있는 사람 태움
if(lastBusHour>personHour||(lastBusHour==personHour&&lastBusMinute>=personMinute)){
nowPeople++;
arrivalTime.erase(arrivalTime.begin());
i--;
}
}
int myHour=0;
int myMinute=0;
// 기다리는 사람이 있는지 확인
// 기다리는 사람 있다면 = 그 사람이 마지막 버스에 탈 수 있는 사람인지 아닌지 확인
if(arrivalTime.size()!=0){
int lastPersonHour = arrivalTime[0].first;
int lastPersonMinute = arrivalTime[0].second;
// 기다리는 사람이 버스에 탈 수 있는 경우 -> 이 사람보다 1분 빨리 와야 함
if(lastBusHour>lastPersonHour||(lastBusHour==lastPersonHour&&lastBusMinute>=lastPersonMinute)){
if(lastPersonMinute==0){
myHour = lastPersonHour-1;
myMinute = 59;
}
else{
myHour = lastPersonHour;
myMinute = lastPersonMinute-1;
}
}
// 기다리는 사람이 버스에 탈 수 없는 경우 -> 버스 도착 시간에 오면 됨
else{
myHour = lastBusHour;
myMinute = lastBusMinute;
}
}
// 기다리는 사람 없다면 -> 버스 도착 시간에 오면 됨
else{
myHour = lastBusHour;
myMinute = lastBusMinute;
}
// 시간 문자화
string myHourStr = "";
string myMinuteStr = "";
if(myHour<10){
myHourStr+="0";
}
myHourStr+=to_string(myHour);
if(myMinute<10){
myMinuteStr+="0";
}
myMinuteStr+=to_string(myMinute);
answer=myHourStr+":"+myMinuteStr;
return answer;
}
회고
구현 문제였고 시간 초과 날 일이 없을 것 같아 쭉 코드 작성한 것 같다.
그런데 버스에 탈 수 있는 사람인지 판별하는 조건문에서 이상하게 생각을 해서 애를 좀 먹은 것 같다.
조건 하나 수정하면 하나 틀리고 또 하나 수정하면 또 문제 생기고 이래서 좀 푸는데 오래 걸린 것 같다.
다음에 문제 풀 때는 귀찮더라도 처음부터 꼼꼼히 작성해야 할 것 같다.