[Programmers] Lv3. [1차] 셔틀버스 | C++

🔗문제 보러가기

프로그래머스

 

 

👨‍💻풀이 과정

 

제 문장 독해력에 하자가 있는건진 몰라도, 처음에 문제 읽고 무슨 소리지 했었습니다. 핵심은 셔틀 버스 운행 횟수인 $n$ 번 내에 사무실에 갈 수 있는 가장 늦은 시간을 고르는 것이었네요. 단순 구현 문제이긴 한데, 시간과 관련된 문제는 항상 계산 부분에서 주의를 기울여야 하는 것 같습니다. 일단은 계산하기 쉽게, string을 int로 변환하는 작업을 먼저 해보죠.

 

1. String 👉🏻 Int로 변환하는 함수 작성

 

주어지는 시간은 "HH:MM" 형태를 띄고 있다고 문제에서 알려주었습니다. 이 문자열에서 시간(hour) 부분과 분(minute) 부분을 추출해야겠네요. 그 후, Int로 변환해서 관리를 할 건데, 관리하기 쉽게 단위를 분(minute)으로 만들겠습니다.

const int UNIT = 60;

int ConvertStringToMinuteInt(const string& time) {
    int hour = stoi(time.substr(0, 2));
    int minute = stoi(time.substr(3, 2));
    return hour * UNIT + minute; 
}

 

2. Int 👉🏻 String으로 변환하는 함수 작성

 

결국 정답으로 리턴해줘야 하는 것은 string이기 때문에, 다시 원래대로 복구하는 작업 또한 필요합니다. 다만, 주의할 점이 시간이든 분이든 모두 두 자리씩 차지한다는 것이죠. 예를 들어, 9시 5분이라도 리턴은 "09:05"로 해주어야 합니다. 이 부분만 주의하면 될 것 같습니다.

string ConvertMinuteIntToString(const int& time) {
    int hour = time / UNIT;
    int minute = time % UNIT;

    string strHour = to_string(hour);
    if (strHour.length() < 2)
        strHour.insert(0, "0");
    
    string strMinute = to_string(minute);
    if (strMinute.length() < 2)
        strMinute.insert(0, "0");

    string result = strHour + ":" + strMinute;
    return result;
}

 

3. 본격적인 로직 구성하기

 

사전 준비는 다 했으니, 이제 본격적으로 로직 구성을 해볼 겁니다. 우선, 주어진 timetable을 int로 변환하여 multiset으로 관리하는 것으로 시작할 겁니다. 1)중복 키 값이 허용되고, 2)삭제에 오버헤드가 적으며, 3)정렬이 된다는 장점이 있기 때문이죠.

int N = timetable.size();
multiset<int> intTimes;

for (int i = 0; i < N; i++)
    intTimes.emplace(ConvertStringToMinuteInt(timetable[i]));

 

 

그 후, 셔틀 버스가 운행 횟수인 $n$ 번 동안 루프를 돌며, 정답이 될 수 있는 후보 시간대들을 배열에 담을 겁니다.

알고리즘은 다음과 같습니다.

1. 버스가 출발해야 하는 시각보다 작거나 같은 탑승객들을 모두 제거하며 카운팅합니다.
   • 버스의 첫 출발 시각은 "09:00" 입니다. 
   • 제거한 탑승객의 시각을 따로 저장해 둡니다.
   • 이 때, 버스에 탄 탑승객이 최대 인원(m)이 된다면 이 로직을 중단합니다.
2. 현재 버스에 탄 탑승객이 최대 인원(m)보다 적다면 "현재 버스 시각"을,
   아니라면 "가장 마지막에 탄 탑승객 시간 - 1"을 후보 시간대로 선정합니다.
   • 가장 마지막에 탄 탑승객보다 1분 빨리 와야, 버스에 탈 수 있으며 가장 늦게 사무실에 갈 수 있습니다.
   • 후보 시간대로 선정한 값을 후보 시간대 배열에 담습니다.
3. 버스 출발 시각을 $t$ 분 더해서 갱신하고, 위 로직을 $n$ 번 반복합니다.
4. 후보 시간대 배열을 내림차순으로 정렬하고, 첫 번째 원소를 String으로 변환하여 리턴합니다.

 

이렇게 함으로써, 문제를 풀 수 있었습니다.

봐주셔서 감사합니다.

 

 

---

✏️소스 코드 및 결과

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int UNIT = 60;

int ConvertStringToMinuteInt(const string& time) {
    int hour = stoi(time.substr(0, 2));
    int minute = stoi(time.substr(3, 2));
    return hour * UNIT + minute; 
}

string ConvertMinuteIntToString(const int& time) {
    int hour = time / UNIT;
    int minute = time % UNIT;

    string strHour = to_string(hour);
    if (strHour.length() < 2)
        strHour.insert(0, "0");
    
    string strMinute = to_string(minute);
    if (strMinute.length() < 2)
        strMinute.insert(0, "0");

    string result = strHour + ":" + strMinute;
    return result;
}

string solution(int n, int t, int m, vector<string> timetable) {
    int N = timetable.size();
    multiset<int> intTimes;

    for (int i = 0; i < N; i++)
        intTimes.emplace(ConvertStringToMinuteInt(timetable[i]));

    int busTime = 9 * UNIT;
    int runCount = 0;

    vector<int> answers;

    while (runCount < n) {
        int passengerCount = 0;
        int lastPassengerTime = 0;

        while (!intTimes.empty() and *intTimes.begin() <= busTime) {
            passengerCount++;
            lastPassengerTime = *intTimes.begin();
            intTimes.erase(intTimes.begin());

            if (passengerCount == m)
                break;
        }

        int boardingTime = (passengerCount < m) ? busTime : lastPassengerTime - 1;
        answers.emplace_back(boardingTime);

        busTime += t;
        runCount++;
    }

    sort(answers.begin(), answers.end(), greater<int>());
    return ConvertMinuteIntToString(answers[0]);
}