[Programmers 코딩 연습] [1차] 셔틀버스 [Level 3]

문제(출처)-프로그래머스

알고리즘

• 시뮬레이션

문제 풀이

콘은 가장 늦게 버스를 타고 싶어한다.
따라서 가장 중점적으로 봐야하는 건 마지막 버스다.

마지막 버스에서 확인해야 하는 것은 무엇일까?

우선 콘은 버스를 타지 않는다고 가정하고 상황을 살펴보자.
첫째로 마지막 버스가 떠날 때 해당 버스에 빈 자리가 있는지 봐야한다.

만약 빈 자리가 있다면, 그냥 맨 뒤에 줄을 서면 된다.
콘은 게을러서 같은 시각에 줄을 서러 온 크루들 중 가장 마지막에 선다고 했으니,
마지막 버스의 도착 시각에 줄을 서면 가장 늦게 버스를 타고서도 사무실로 갈 수 있을 것이다.

둘째로 빈 자리가 없다면, 마지막으로 버스를 타게 된 크루의 도착 시각을 봐야한다.
콘은 같은 시각에 도착했으면 마지막에 줄을 선다고 했으니 마지막 크루보다 더 일찍 도착해야만 한다. 시각은 1분 단위이므로 해당 크루의 도착 시각에서 1분을 빼자.

대강의 설계

1. 입력으로 주어지는 timetable을 순서대로 정렬하자. (비내림 차순)
2. 조건에 맞게 마지막 버스까지 승객을 태우기를 시뮬레이션으로 돌리자.
3. 마지막 버스의 상태를 본다.
   3-1. 빈 자리가 있다면, 버스의 도착 시간이 답.
   3-2. 빈 자리가 없다면, 마지막으로 탄 크루의 도착 시각 - 1분이 답.

• 시뮬레이션을 돌릴 때, 벡터를 그대로 쓰면 지저분할 것 같아서 queue를 사용했다.
• 시각은 모두 정수 타입 및 분 단위로 바꿔서 계산한 뒤, 마지막 답만 string으로 형식에 맞게 변경했다.

소스코드

cpp

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    queue<int> que;
    int bus_time = 540; // 버스 도착 시각
    int last_crew_time; // 가장 최근에 탄 승객이 줄 선 시각
    int answer_time, i;
    int hour, min;
    
    sort(timetable.begin(), timetable.end());
    
    for (string &time : timetable) {
        hour = stoi(time.substr(0,2));
        min = stoi(time.substr(3,2));
        que.push(hour*60+min);
    }
    
    while (n--) {
        // 크루들 버스 태우기
        for (i = 0; i < m && !que.empty(); i++) {
            int crew_time = que.front();
            
            if (crew_time > bus_time)    // 버스 탈 수 없음
                break;
            
            que.pop();
            last_crew_time = crew_time;
        }
        
        // 다음 버스 도착 시각 계산
        bus_time += t;
    }

    if (i < m)                          // 마지막 버스에 빈자리가 있다.
        answer_time = (bus_time - t);   // 따라서 마지막 버스의 도착 시각에 줄 서면 된다.
    else if (i == m)                        // 마지막 버스에 빈자리가 없다.
        answer_time = last_crew_time - 1;   // 따라서 마지막 승객의 도착 시각보다 1분 빨리 줄을 서면 된다.
    
    min = answer_time % 60;
    hour = answer_time / 60;
    
    if (hour < 10) answer += "0"+to_string(hour);
    else answer += to_string(hour);
    
    answer += ":";
    
    if (min < 10) answer += "0"+to_string(min);
    else answer += to_string(min);
    
    return answer;
}