프로그래머스[Programmers] - 셔틀버스(C++)[LV3]

📕문제

https://school.programmers.co.kr/learn/courses/30/lessons/17678

프로그래머스

---

🔎문제 풀이

우선 문제 이해하는데 조금 오래 걸렸습니다.

제가 이해한 내용을 설명하자면,

변수 n, t, m이 있습니다.

n은 운행하는 버스의 수, t= 배차 간격, m= 탑승할 수 있는 인원의 수입니다.

 

timetable은 이제 기다리는 크루원들의 도착시간입니다.

그림이 이상하더라도 양해 부탁합니다.. ㅎ 🙏

위 그림은 입출력예제 1번입니다.

 

여기서 가장 기본이 되는 정보는 09:00에 처음 버스가 운행한다입니다.

지금 기다리고 있는 사람이 4명이고 탑승정원은 5명이므로,

우리의 주인공 콘은 느긋하게 버스가 도착하는 시간인 09:00에 도착하면 버스를 타고 갈 수 있습니다.

따라서 답이 09:00인것입니다.

 

다음 그림을 예로 들어서 설명해 드리겠습니다.

위 그림은 두 번째 예제입니다.

버스는 2대이고, 배차 간격은 10분이며 탑승정원은 2명입니다.

 

버스가 처음 도착한 09:00에는 08:00부터 기다린 크루원이 탈 수 있습니다.

그 뒤에 09:09와 09:10에 기다린 크루들은 다음 차를 타야 합니다.

 

그다음 버스는 09:10분에 도착합니다.

현재 기다리고 있는 크루원들은 2명이고, 09:09와 09:10분에 도착했습니다.

여기서 콘이 타기 위해서는 언제 도착해야 할까요??

콘은 게으르기 때문에 버스를 타지만, 가능한 늦게 도착하고 싶어 합니다.

따라서 콘은 09:09에 도착해야 할 것입니다.

이렇게 되면 09:09에 기다린 크루원과 콘이 버스를 탈 수 있습니다.

 

콘이 버스를 탈 수 있는 방법에는 2가지 경우의 수가 있습니다.

---

📦정원의 여유가 있어, 콘이 여유롭게 버스를 탈 수 있는 경우

첫 번째 그림의 예제가 해당됩니다.

기다리는 정원이 다 타더라도, 정원의 여유가 있으면, 콘은 버스가 도착하는 시간에 정류장에 가면 됩니다.

---

📦정원의 여유가 없어서, 콘이 중간에 끼어들어야 하는 경우

두 번째 그림의 예제가 해당됩니다.

정원이 없는 경우 마지막에 탄 크루원을 내보내고, 콘이 타야 합니다.

그렇다면 콘이 도착해야 하는 시간은 언제일까요?

바로 마지막에 탄 크루원보다 1초라도 빨리 도착하면 탈 수 있으므로, 

마지막 크루원보다 1초 빨리 도착하는 시간입니다.

---

크루원들의 도착 시간은 오름차순으로 정렬되어 있으면 좋겠지만,, 입출력 예제만 봐도 무작위로 줬기 때문에,

크루원들의 도착시간을 오름차순으로 정렬을 해야 합니다.

 

저는 timetable에 해당하는 시간들을 모두 분으로 치환해서, 저장했습니다.

예를 들어서 12:00에 도착했다면 720분으로 치환을 해서 저장했습니다.

이렇게 치환한 분들을 배열에 저장해서, 오름차순으로 정렬합니다.

 

그리고 기억해야 할 정보인 버스 첫차 시간은 09:00이므로, 분으로 치환하면 540분이 될 것입니다.

 

풀이 과정

1. 버스를 1대~n대까지 반복문을 돌립니다.
2. 배차 간격을 이용해서 버스가 도착하는 시간을 계산합니다.
   • 버스가 도착하는 시간 내의 크루원이 도착한다면 탑승인원들을 더해줍니다.
   • 더해주다가, 만약 정원까지 꽉 찼다면, 1번 과정부터 시작합니다.
3. 만약 버스가 n대까지 도달했을 경우
   • 탑승인원이 m명이라면 콘은 맨 마지막에 탑승한 인원보다 1초 빨리 도착해야 합니다.
   • 탑승인원이 m명이 아니라면, 콘은 버스가 도착한 시간에 도착하면 됩니다.
4. 콘이 도착한 시간을 다시 HH:MM으로 치환해 주면 끝입니다.

---

💻코드

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<int>wait;
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    for(int i=0; i<timetable.size();i++){
        int w_time = (timetable[i][0]-'0')*600+(timetable[i][1]-'0')*60
            +(timetable[i][3]-'0')*10+(timetable[i][4]-'0');//시간을 분으로 치환
        wait.push_back(w_time);
    }
    sort(wait.begin(),wait.end());
    //막차를 타고 갈 수 있나? m과 timetable의 수를 비교해보자
    //우선 첫차는 09:00이다. 첫차를 시간으로 바꾸면 540분.
    int first_start=540;
    int last=0,reuslt=0,idx=0,tt=0;
    for(int bus = 1; bus<=n; bus++){ //bus가 1대부터 n대까지
        int cnt=0; 
        tt=first_start+(bus-1)*t;
        for(int k=idx; k<wait.size();k++){ //기다리는 사람들.
            if(cnt==m) //만약 탄 횟수가 정원과 같아디면 탐색 종료.
                break;
            if(tt>=wait[k]){ //일찍 와서 기다린 경우                           
                cnt++;
                idx++;
            }
            else //오름차순이므로 그 이후는 검사할 필요가 없음.
                break;             
        }
        if(bus==n){
            if(cnt==m)//버스가 찻는데 만약 정원이 꽉 찻다면,그 이전거를 타면 될거임.
                result = wait[idx-1]-1;//맨 마지막 도착한 사람보다 빨리 와야함
            else//만약 다 차지 않앗다면 그냥 버스 도착하는 시간에 오면됨.
                 result = tt;            
        }
    }
    //result를 600으로 나누면 1, 
    int HH = result/600;
    result%=600;
    int H = result/60;
    result%=60;
    int MM = result/10;
    result%=10;
    int M = result;
    answer = to_string(HH)+to_string(H)+":"+to_string(MM)+to_string(M);
    return answer;
}

 

 

💡주석을 봐도 이해가 안된다면 질문 부탁드립니다!