Programmers - 셔틀버스

---

title: Programmers - 셔틀버스
date: 2022-07-21
tags:

• Algorithm

---

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

문제 요약

셔틀은 0900부터 n회 t분 간격으로 m명씩 수송한다.
크루들이 언제부터 줄을 서는지 알며, 콘은 게으르기에 동일한 시각이라면 뒤에 줄을 선다.
콘이 셔틀버스를 꼭 타야하며, 제일 늦은 시각에 줄을 선다. 이 시각을 찾아 문자열로 return한다.

문제 풀이

구현 아이디어 자체는 간단하나, 구현 난이도가 있는 문제이다.
크루들을 앞에서부터 태우며, 크루들이 전부 타 자리가 없는 경우, 그 크루들이 타는 시각보다 1분 일찍 줄을 서면 된다.
생각보다 예외처리를 해줘야 하는 부분이 많아 번거로운 문제이다.


우선 다른 크루들이 서는 시각을 정리해야 한다. 동일한 시각에 서는 크루들도 있으므로, 같은 시각의 크루들을 묶어서 정리한다.
HH:MM 방식의 시각이므로 전부 Minute 단위로 바꾸어 묶어서 저장한다.
이후, 셔틀 운행 횟수인 n번만큼 loop를 하여 크루를 한 명씩 태운다.
처음에는 총 수송 가능 인원인 n * m을 이용한 loop를 하였으나, 매 셔틀 시각에 줄을 서 있는 크루들만 태울 수 있다.
그러므로 각 셔틀이 도착하는 타이밍에 줄을 선 크루들을 확인해야 하며, 처리가 귀찮아질 것 같아 loop를 하나 더 사용하였다.
줄을 선 크루를 한 명씩 태우며, 줄을 선 모든 크루들이 타거나 셔틀버스의 자리가 꽉 찰 경우 loop가 종료된다.
모든 크루들이 탔다면 빈 자리가 있을 것이며, 이 경우 셔틀버스가 마지막으로 도착하는 시각에 줄을 서면 된다.
셔틀버스의 자리가 꽉 찰 경우, 마지막으로 줄을 선 크루들의 시각을 알고 있다. 이 시각보다 1분 일찍 줄을 선다.


이 셔틀버스 문제는 셔틀버스와 같은 운송 수단의 운행 횟수, 간격, 운행하는 차량 수 등을 조정할 때 응용할 수 있는 문제이다. 지하철에도 적용하기 좋다.
현재의 운행 체계에서 인원이 넘치는 경우도 있을 것이고, 아무도 탑승하지 않아 낭비되는 경우도 있을 것이다.
낭비되는 경우 운행을 줄이고, 인원이 넘치는 경우 더욱 많은 크루들이 탑승할 수 있도록 운행 체계를 조정해야 한다.

프로그램

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

using std :: string ;
using std :: vector ;
using std :: pair ;
using std :: make_pair ;

vector < pair < int , int > > getTimeOfStringWithSorted ( vector < string > vStringTime , int iMaxTime )
{
    int iStringSize = vStringTime.size () ;
    vector < pair < int , int > > vIntTime ;
    int iFormerTime = -1 ;
    int iCount = 0 ;



    std :: sort ( vStringTime.begin () , vStringTime.end () ) ;

    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        const char * cpString = vStringTime [ i ].data () ;
        int iCurrentTime = ( cpString [ 0 ] - '0' ) * 600 + ( cpString [ 1 ] - '0' ) * 60 + ( cpString [ 3 ] - '0' ) * 10 + ( cpString [ 4 ] - '0' ) ;




        if ( ( 0 != iCount ) && ( iFormerTime != iCurrentTime ) )
        {
            vIntTime.emplace_back ( make_pair ( iFormerTime , iCount ) ) ;
            iCount = 0 ;
        }
        if ( iMaxTime < iCurrentTime )        // Exceed last time, no need to count
        {
            iMaxTime = -1 ;

            break ;
        }

        if ( 0 == iCount )
        {
            iFormerTime = iCurrentTime ;
            iCount = 1 ;
        }
        else if ( iFormerTime == iCurrentTime )
        {
            ++ iCount ;
        }
    }

    if ( -1 != iMaxTime )
        vIntTime.emplace_back ( make_pair ( iFormerTime , iCount ) ) ;

    return vIntTime ;
}

string solution ( int n , int t , int m , vector < string > timetable )
{
    string answer = "" ;
    int iFinalShuttleArrive = 540 + ( n - 1 ) * t ;
    vector < pair < int , int > > vTime = getTimeOfStringWithSorted ( timetable , iFinalShuttleArrive ) ;    // Time , count
    int iTableSize = vTime.size () ;
    int iLineupTime = -1 ;
    int iLineupCount = 0 ;
    int iLineupIndex = -1 ;
    int iRideCount = 0 ;



    for ( int i = 0 ; i < n ; ++i )
    {
        iRideCount = ( n - i ) * m ;

        while ( ( n - i - 1 ) * m != iRideCount )
        {
            if ( 0 == iLineupCount )
            {
                if ( iLineupIndex + 1 == iTableSize )        // Everyone ride
                    break ;

                pair < int , int > pTimeInfo = vTime [ ++ iLineupIndex ] ;
                iLineupTime = pTimeInfo.first ;
                iLineupCount = pTimeInfo.second ;
            }
            if ( 540 + i * t < iLineupTime )                // Current people arrive late
                break ;

            -- iLineupCount ;
            -- iRideCount ;
        }
    }


    if ( 0 < iRideCount )            // Can ride at the last
    {
        iLineupTime = iFinalShuttleArrive ;
    }
    else                            // Need to come early
    {
        -- iLineupTime ;
    }

    answer += std :: to_string ( iLineupTime / 600 ) ;
    answer += std :: to_string ( iLineupTime % 600 / 60 ) ;
    answer += ":" ;
    answer += std :: to_string ( iLineupTime % 60 / 10 ) ;
    answer += std :: to_string ( iLineupTime % 10 ) ;


    return answer ;
}