[ 프로그래머스 셔틀버스 (Lv3) ] (C++)

프로그래머스의 셔틀버스(Lv3) 문제이다.

 

[ 문제풀이 ]

콘이 셔틀버스를 타고 출근을 할 때, 가장 늦게 출근할 수 있는 시간을 구해야 하는 문제이다.

먼저, 주어진 변수들을 관리하는 방법부터 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 시간 변수 관리

이 문제에서 주어진 핵심 변수들은 모두 "시간" 으로 표현이 되어 있다.

셔틀이 처음 출발하는 시간 , 크루원들이 대기열에 도착하는 시간 , 우리가 구해야 하는 정답 모두 "시간"의 개념으로 표시가 되어 있다. 하지만 ! 시간이 int형 자료형이 아닌 문자열 형태로 주어지게 된다. 조금 더 구체적으로 이야기해보면 HH:MM 형태로 "시"와 "분"의 형태로 주어지게 된다.

문자열로 숫자가 주어지기 때문에, 본인은 이를 간편하게 계산하기 위해서 모두 "분" 단위로 변환 후 계산을 진행해 주었다.

"HH:MM" 이라는 문자열이 주어진다면 이를 분 단위의 시간으로 바꾸게 되면 HH * 60 + MM 으로 표현할 수 있다.

이런식으로 변환을 하게 되면 첫 번째 셔틀이 출발하는 시간은 "540"이 된다. 09:00에 처음으로 출발을 하기 때문이다.

 

#2. Solution

본인은 크루원들이 대기열에 도착하는 시간을 #1의 과정을 통해 '분'단위로 모두 통일 후 오름차순으로 정렬시켜 주었다.

크루원들이 대기열에 도착하는 시간이 오름차순으로 주어진다는 이야기가 없으므로, 크루원들의 도착시간을 오름차순으로 관리해 주었고, 이 오름차순으로 정렬되어 있는 크루원들 시간들 사이에 콘이 들어갈 시간을 찾으면 되는 것이다.

그렇다면, 콘이 셔틀을 타기 위해서 가장 늦게 도착할 수 있는 시간을 한번 구해보자. 

콘이 가장 늦게 출근을 하기 위해서는 무조건적으로 "가장 마지막 셔틀에 탑승하는 것" 이 유리할 것이다.

즉 ! 우리는 콘을 반드시 가장 마지막 셔틀에 탑승하게 만들 것이다. 지금부터 이 과정을 크게 2가지 경우로 나눠서 생각을 해보자.

1. 마지막 셔틀에 자리가 남는 경우

가장 마지막 셔틀에 딱 맞춰서 크루원들이 다 탔을수도 있고, 그 전 셔틀에 이미 탑승을 완료했을 수도 있다. 이건 상관이 없다. 중요한건, "가장 마지막 셔틀에 자리가 남는 다는 것" 이다. 가장 마지막 셔틀에 자리가 남는다면 이 셔틀버스를 타고 가면 된다.

즉 ! 이 때의 정답은 "가장 마지막 셔틀이 도착하는 시간"이 될 것이다. 가장 마지막 셔틀이 도착하는 시간에만 대기열에 들어가 있으면 가장 마지막 셔틀을 탈 수 있음을 의미하기 때문이다.

"마지막 셔틀에 자리가 남을 경우 , 콘이 줄을 서야 하는 시간은 가장 마지막 셔틀이 도착하는 시간"

2. 마지막 셔틀에 자리가 남지 않는 경우

마지막 셔틀에 자리가 남지 않는다면, 콘은 출근을 할 수 없음을 의미한다. 즉 ! 이 경우에는 콘이 크루원들이 도착하는 시간 중간 어디간에 먼저 도착을 해 있어야만 마지막 셔틀을 탈 수 있음을 의미한다.

그럼 한가지 예를 가지고 생각을 해보자.

ex_A)

마지막 셔틀 버스가 5분에 도착하고 현재 줄을 서 있는 크루원이 [ 4분 , 5분 ] 에 도착한 2명의 크루원이 있다고 가정해보자.

그리고 셔틀버스의 탈 수 있는 최대 크루원의 수는 2명이라고 가정해보자.

콘을 제외하고 생각한다면, 4분과 5분에 도착한 크루원 2명이 마지막 셔틀버스를 탈 것이다. 하지만 우리는 콘을 반드시 탑승을 시켜야 한다. 그렇다면 콘은 몇 분에 줄을 서야할까 ?? 4분에 줄을 서면 될 것이다.

그렇게 되면 현재 줄을 서 있는 크루원이 [ 4분 , 4분(콘) , 5분 ] 형태로 될 것이고, 마지막 셔틀버스에 콘이 탈 수 있을 것이다.

한가지 상황을 더보자.

 

ex_B)

마지막 셔틀버스가 5분에 도착하고 현재 줄을 서 있는 크루원이 [ 5분 , 5분 , 6분 ] 에 도착한 3명의 크루원이 있다고 가정해보자. 그리고 셔틀 버스의 탈 수 있는 최대 크루원의 수는 2명이라고 가정해보자.

콘을 제외하고 생각한다면, 5분에 줄을 선 크루원 2명이 탑승을 할 것이다. 콘이 탑승하기 위해서는 4분에 줄을서야 할 것이다.

왜냐하면 ! 5분에 줄을 서게 되면 "같은 시간에 도착한 크루원들 중에서는 가장 마지막에 줄을 서는 콘의 특징" 때문에 셔틀버스를 탈 수 없게 될 것이다.

 

그럼 콘이 셔틀버스를 탈 수 있는 구체적인 시간을 이야기해보자.

바로 ! "가장 마지막에 탑승한 크루원의 시간 - 1"을 한 시간이 콘이 셔틀버스를 탈 수 있는 시간이 된다.

ex_A)에서 가장 마지막에 탑승한 크루원의 시간은 '5분' 이였다. 그리고 콘이 셔틀버스를 탈 수 있는 시간은 5 - 1 = 4분이었다.

ex_B)에서 가장 마지막에 탑승한 크루원의 시간은 '5분' 이였다. 그리고 콘이 셔틀버스를 탈 수 있는 시간은  5 - 1 = 4분이었다.

"마지막 셔틀에 자리가 남지 않는 경우, 콘이 줄을 서야 하는 시간은, 콘을 제외하고 생각했을 때, 셔틀버스를 탑승한 마지막 크루원의 시간 - 1"

 

#3. 코드

	int Shuttle_Time = 540;
	int Crew_Idx = 0;
	int Answer_Time;
	for (int i = 1; i <= n; i++, Shuttle_Time = Shuttle_Time + t)
	{
		int Cnt = 0;
		for (int j = Crew_Idx; j < Crew.size(); j++)
		{
			if (Crew[j] <= Shuttle_Time)
			{
				Crew_Idx++;
				Cnt++;
				if (Cnt == m) break;
			}
		}

		if (i == n)
		{
			if (Cnt == m) Answer_Time = Crew[Crew_Idx - 1] - 1;
			else Answer_Time = Shuttle_Time;
		}
	}

본인이 구현한 코드이다. 위에서 Crew라는 변수는 vector이다. 크루원들의 대기열 도착 시간을 오름차순으로 정렬해놓은 Vector이다.

가장 마지막 조건문인 if(i == n)을 살펴보게 되면, "마지막 셔틀 버스일 경우" 를 의미하는 조건문이다.

우리는 콘을 무조건 마지막 셔틀버스에 탑승시킬 것이다.

그 안의 조건문들을 보게되면, "마지막 셔틀 버스에 자리가 없는경우" 와 "자리가 남는경우" 콘의 도착시간을 결정하는 조건문들이 존재한다.

그 위의 반복문을 보게되면 "크루원들의 도착시간에 따라서 순차적으로 셔틀버스에 탑승하는 상황" 을 구현한 것이다.

만약, 셔틀버스에 정원이 가득 찬다면, 그 다음 크루원은 다음 셔틀버스를 타게 되는 것이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
string solution(int n, int t, int m, vector<string> timetable) 
{
    vector<int> Crew;
    for (int i = 0; i < timetable.size(); i++)
    {
        string S_Hour = "";
        S_Hour = S_Hour + timetable[i][0];
        S_Hour = S_Hour + timetable[i][1];
        int Hour = stoi(S_Hour);
        
        string S_Minute = "";
        S_Minute = S_Minute + timetable[i][3];
        S_Minute = S_Minute + timetable[i][4];
        int Minute = stoi(S_Minute);
        
        int Time = Hour * 60 + Minute;
        Crew.push_back(Time);
    }
    sort(Crew.begin(), Crew.end());
 
    int Shuttle_Time = 540;
    int Crew_Idx = 0;
    int Answer_Time;
    for (int i = 1; i <= n; i++, Shuttle_Time = Shuttle_Time + t)
    {
        int Cnt = 0;
        for (int j = Crew_Idx; j < Crew.size(); j++)
        {
            if (Crew[j] <= Shuttle_Time)
            {
                Crew_Idx++;
                Cnt++;
                if (Cnt == m) break;
            }
        }
 
        if (i == n)
        {
            if (Cnt == m) Answer_Time = Crew[Crew_Idx - 1] - 1;
            else Answer_Time = Shuttle_Time;
        }
    }
    
    string answer = "";
    int Hour = Answer_Time / 60;
    int Minute = Answer_Time % 60;
    char A = Hour / 10 + '0';
    char B = Hour % 10 + '0';
    char C = Minute / 10 + '0';
    char D = Minute % 10 + '0';
    answer = answer + A;
    answer = answer + B;
    answer = answer + ':';
    answer = answer + C;
    answer = answer + D;
    return answer;
}