문제 푼 날짜 : 2021-07-18

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17678

접근 및 풀이

시간 계산의 편의를 위해 "HH:MM" 꼴로 이루어진 각 크루들의 도착시간을 분으로 변환하여 주었고, 오름차순으로 정렬해주었다.
코드는 아래의 알고리즘을 따라서 구현하였다.

1. 셔틀버스가 출발하는 시간(기준시간) 이전부터 대기중인 인원들을 태운다.
2. 태우면서 셔틀버스 정원과 몇 번째 크루까지 태웠는지 체크해준다.
3. 현재 셔틀이 마지막 셔틀인 경우,
   3-1. 대기줄이 꽉 차있으면 (마지막 사람 도착시간 - 1)에 도착
   3-2. 자리가 있으면 그냥 기준시간에 도착
4. 마지막 셔틀이 아닌 경우 다음 셔틀 출발시간을 배차시간으로 변경 후 1.부터 반복

코드

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    
    vector<int> crew;
    for (string str : timetable) {
        string HH = str.substr(0, 2);
        string MM = str.substr(3);
        
        int time = stoi(HH) * 60 + stoi(MM); // 분으로 전환
        crew.push_back(time);
    }
    sort(crew.begin(), crew.end());
    
    int start = 540;
    int conTime = 0;
    int passenger = 0; // 탑승객 체크
    for (int i = 0; i < n; i++) {
        int limit = 0;
        for (int j = passenger; j < crew.size(); j++) {
            if (crew[j] <= start) { // 셔틀 출발시간 전에 대기중인 사람들이면 모두 탑승
                passenger++;
                limit++;
            }
            if (limit == m) { // 정원이 꽉차면
                break;
            }
        }
        
        if (i + 1 == n) { // 현재 셔틀이 마지막 셔틀이면
            if (limit == m) { // 이미 대기줄 꽉 찼으면
                conTime = crew[passenger - 1] - 1; // 대기줄의 마지막 사람보다 1분 일찍오기
            } else { 
                conTime = start; // 자리 있으면 그냥 기준시간에 도착
            }
        } else { // 마지막 셔틀이 아니면
            start += t; // 다음 배차시간으로 넘어감
        }
    }
    
    // "HH:MM" 형식으로 변환
    int H = conTime / 60;
    int M = conTime % 60;
    string hr = "", min = "";
    if (H < 10) {
        hr = "0" + to_string(H);
    } else {
        hr = to_string(H);
    }
    if (M < 10) {
        min = "0" + to_string(M);
    } else {
        min = to_string(M);
    }
    answer = hr + ":" + min;
    
    return answer;
}

결과

피드백

문제보고 쫄지말고 우선 생각을 정리하는 연습을 해야겠다.