[프로그래머스/C++] 셔틀버스

 

문제

문제 설명

 

풀이

 

 

특별한 알고리즘 없이 그리디하게 풀 수 있는 문제였다.

먼저 특정 시간에 버스가 오면 그 때, 탈 수 있는지 없는지를 판단한다.

​

만약 탈 수 있다면 버스가 도착하는 시간에 나와서 타면 된다.

​

문제는 버스 탑승 인원만큼 서 있을 때가 문제다.

만약 버스 탑승 인원 만큼 서 있다면, 마지막에 버스에 탑승하는 사람보다 1분 빠르게 줄을 서면 된다.

(마지막에 줄을 서 있는 인원이 아니라 마지막에 버스에 탑승하는 인원이다.)

​

요약하면 탑승시간 변수에 버스가 오는 시간을 저장한다.

만약 그 시간에 탑승하는 인원들이 많아 버스의 탑승인원과 같거나 많아지면 마지막에 탑승하는 인원의 탑승시간보다 1분 빨리나오도록 한다.

버스의 운행 횟수만큼 위 과정을 반복하면, 제일 늦게 버스를 탈 수 있다.

​

​

[아이디어 정리]

1. 버스가 올 때마다 줄 서 있는 인원 중 버스를 탈 수 있는 사람의 수를 세며 count를 1씩 늘린다.
2. 만약 count가 버스의 최대 탑승인원과 같아지면, 다음 인덱스를 st에 저장하고 내 탑승 시간을 마지막 인원의 시간에서 -1분을 뺀 값으로 저장한다.
3. ​그 뒤에 오는 버스가 있다면, 버스의 도착시간으로 내 탑승시간을 수정하고, 다시 버스를 탈 수 있는 인원을 센다.
4. ​위 과정을 반복해 최종적으로 나오는 값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    vector<int> realTable;
    int num=0;
    for (int i=0; i<timetable.size(); i++)
    {
        num=stoi(timetable[i].substr(0,2))*60+stoi(timetable[i].substr(3,2));
        realTable.push_back(num);
    }
    sort(realTable.begin(),realTable.end());
    int st=0;
    int stTime, ridePerson, myTime;
    for (int i=0; i<n; i++) //n번 운행
    {
        ridePerson=0;
        stTime=9*60+i*t;
        myTime=9*60+i*t;
        for(int j=st; j<realTable.size(); j++)
        {            
            if (realTable[j]<=stTime)
            {
                ridePerson+=1;    
            }
            else // 시간이 초과됨
            {
                st=j;
                break;
            }
            if (ridePerson==m) // 버스 인원이 다 참, 다음 인덱스부터 시작해야 함
            {
                st=j+1;
                myTime=realTable[j]-1;
                break;
            }
        }
    }
    string minuite,hour;
    hour=to_string(myTime/60);
    minuite=to_string(myTime%60);
    if (hour.length()<2)
    {
        hour="0"+hour;
    }
    if (minuite.length()<2)
    {
        minuite="0"+minuite;
    }
    string answer=hour + ":" + minuite;   
    return answer;
}

 

---

 

문자를 숫자로 숫자를 문자로 변환하는게 더 힘든 문제였다...

 

 

프로그래머스