프로그래머스 문제 - [1차] 셔틀버스

프로그래머스 퍼즐 조각 채우기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

무료 셔틀버스가 운행하며 처음 버스는 오전 9시이고 t분 간격으로 n회 버스가 추가 운행됩니다.
각 버스는 m명의 승객이 탈 수 있으며 도착한 순간 대기열에 선 승각까지 태우고 출발합니다.
즉 9시에 온 승객도 9시 버스에 탈 수 있습니다.
승객인 콘은 어떤 승객이 대기열을 서는지 알아내었습니다.
콘이 셔틀버스를 타는 시각 중 제일 늦은 시각을 구하여라

문제 풀이

제일 늦은 시간을 구하는 것이고, 시간을 기준으로 먼저 온 사람들이 버스에 탑승하기 때문에 주어진 대기열을 오름차순으로 정려해줍니다.

priority_queue<string, vector<string>, greater<string>> pq;
//시간이 빠른 순으로 정렬
for(string str : timetable)
{
    pq.push(str);
}

이후 셔틀버스가 오는 시간마다 제일 빨리 오는 승객의 시간을 비교하며 승객을 태워줍니다.
마지막 버스에 마지막 자리를 마지막 손님이 타는 경우도 존재하기에 전에 탑승했던 승객의 시간을 저장해줍니다.

for(int i = 0; i < n; i++)
{
    //셔틀버스가 오는 시간 계산
    if(i != 0)
    {
        minute += t;
        hour += minute / 60;
        minute = minute % 60;
    }
    for(int j = 0; j < m; j++)
    {
        //대기줄의 사람이 있는지 확인
        if(!pq.empty())
        {
            curHour = stoi(pq.top().substr(0, 2));
            curMinute = stoi(pq.top().substr(3, 2));
            //만약 버스가 오는 시간보다 더 빠른 시간으로 온 사람이 있는지 확인
            if(hour > curHour || hour >= curHour && minute >= curMinute)
            {
                pq.pop();
            }
        }
        else
        {
            curHour = -1;
            curMinute = -1;
        }
    }
}

마지막 버스까지 승객과 비교 후 제일 늦게 탈 콘의 자리를 찾아주는데 고려해야 할 사항이 2가지 있습니다.
1.대기줄에 사람이 없으며 제일 늦은 버스가 왔을 때 콘이 탈 자리가 있는지 확인
2.대기줄에 사람이 있지만 제일 늦은 버스가 올 때 그 손님이 아직 올 시간이 안됬을 경우
이런 상황을 고려하여 시간을 구해줍니다.

//대기줄에 사람이 없고 제일 늦은 버스에 빈 자리가 있다면
if(curHour == -1 && curMinute == -1)
{
    answer = timeSetting(hour) + ":" + timeSetting(minute);
}
else
{
    if(curMinute == 0)
    {
        curMinute = 59;
        curHour--;
    }
    else
    {
        curMinute--;
    }
    //올 사람이 있지만 버스보다 늦을 경우
    if(hour < curHour || hour <= curHour && minute <= curMinute)
    {
        answer = timeSetting(hour) + ":" + timeSetting(minute);
    }
    else
    {
        answer = timeSetting(curHour) + ":" + timeSetting(curMinute);
    }
}

전체 코드

이번 문제는 여러 상황을 고려하며 풀어가면 충분히 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

string timeSetting(int time)
{
    if(time < 10)
    {
        return to_string(0) + to_string(time);
    }
    else
    {
        return to_string(time);
    }
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    priority_queue<string, vector<string>, greater<string>> pq;
    //시간이 빠른 순으로 정렬
    for(string str : timetable)
    {
        pq.push(str);
    }
    
    int hour = 0;
    int minute = 0;
    int curHour, curMinute;
    
    hour = 9;
    for(int i = 0; i < n; i++)
    {
        //셔틀버스가 오는 시간 계산
        if(i != 0)
        {
            minute += t;
            hour += minute / 60;
            minute = minute % 60;
        }
        for(int j = 0; j < m; j++)
        {
            //대기줄의 사람이 있는지 확인
            if(!pq.empty())
            {
                curHour = stoi(pq.top().substr(0, 2));
                curMinute = stoi(pq.top().substr(3, 2));
                //만약 버스가 오는 시간보다 더 빠른 시간으로 온 사람이 있는지 확인
                if(hour > curHour || hour >= curHour && minute >= curMinute)
                {
                    pq.pop();
                }
            }
            else
            {
                curHour = -1;
                curMinute = -1;
            }
        }
    }
    //대기줄에 사람이 없고 제일 늦은 버스에 빈 자리가 있다면
    if(curHour == -1 && curMinute == -1)
    {
        answer = timeSetting(hour) + ":" + timeSetting(minute);
    }
    else
    {
        if(curMinute == 0)
        {
            curMinute = 59;
            curHour--;
        }
        else
        {
            curMinute--;
        }
        //올 사람이 있지만 버스보다 늦을 경우
        if(hour < curHour || hour <= curHour && minute <= curMinute)
        {
            answer = timeSetting(hour) + ":" + timeSetting(minute);
        }
        else
        {
            answer = timeSetting(curHour) + ":" + timeSetting(curMinute);
        }
    }
    
    return answer;
}

출처

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