[C++로 풀이] 셔틀버스⭐⭐⭐

Date: 2021.03.19 Updated: 2021.03.19

Categories: Programmers

Tags: Coding Test Algorithm

📌 셔틀버스

난이도 ⭐⭐⭐

🚀 문제

🔥 문제 설명

첫 버스는 무조건 09 : 00 에 온다.
같은 시간에 온 사람들이 선 줄에서 콘은 언제나 맨 뒤에 줄선다.
버스 오는 시간에 줄 선 사람도 버스에 탈 수 있다.

콘은 게으르기 때문에 마지막 버스 타고 출근할 수 있는, 최대한 늦게 줄을 서는 시간의 그 마지노선를 구하는 문제이다.

n은 버스의 수, t는 간격, m은 버스에 탑승할 수 있는 최대 인원.

입출력 예제 1 👉 09:00
- 버스는 딱 1번 온다. 즉 09:00 버스 하나 밖에 없다. 이미 09:00 전에 4 명이 줄서있는데 버스는 최대 5명까지 태울 수 있으므로 콘은 무난하게 09:00 에 와도 된다.
입출력 예제 2 👉 09:09
- 버스는 10분 간격으로 2 번 오기 때문에 09:00, 09:10 이렇게 온다. 콘은 09:10 버스를 타야한다. 08:00 에 줄 선 크루는 09:00 버스를 타고 출근할테고, 09:09, 09:10 에 줄 선 크루들이 09:10 버스를 탈 것이다. 버스의 정원은 2 명이기 때문에 09:10 에 줄을 선 크루보다 콘이 더 일찍 와야한다는 소리이다. 콘은 항상 같은 시간에 온 사람들보다 맨 뒤에 오기 때문에 09:09 에 와도 09:09 인 사람이 딱 2명이 되는거라 버스 정원을 초과하지 않는다. 즉, 콘은 09:09 에 와야 09:10 마지막 버스를 탈 수 있다. (09:10 에 줄서는 크루는 버스 못 타겠지..☆)
입출력 예제 3 👉 08:59
- 버스의 정원은 2 명이며, 09:00, 09:01 이렇게 2 번 온다. 이미 09:00 에 줄 서 있는 사람만 4명이기 때문에 이 사람들이 2 명씩 09:00, 09:01 버스에 나눠타게 된다. 콘은 같은 시간에 온 사람들 중에서 가장 뒤에 줄을 서기 때문에 09:00 에 오면 콘은 두 버스 모두에 타지 못한다.(5번째가 되서) 따라서 콘은 08:59 에 줄을 서야 버스를 탈 수 있게 된다.
입출력 예제 4 👉 00:00
- 예제 3 처럼 00:01 에 온 5 명이 전부 5명 정원인 버스를 딱 한번 09:00에 오는 버스에 모두 타버릴 것이기 때문에 콘은 00:01 보다 더 일찍 와야 한다. 00:01에 줄을 서면 콘은 00:01 에 온 사람들 중 6번째가 되기 때문에 못 탄다. 그러므로 콘은 00:00 에 줄을 서야 한다.
입출력 예제 5 👉 09:00
- 버스는 09:00 에 딱 한번 오며 한 명만 태울 수 있다. 줄 서는 크루가 23:59 에 한명 뿐이니 콘은 편하게 09:00 에만 오면 된다.
입출력 예제 6 👉 18:00
- 버스가 1시간 단위로 09:00, 10:00, .. ,18:00 에 10 번 오게 된다. 줄 선 사람이 모두 23:59 라서 콘은 그냥 18:00 에만 오면 마지막 버스 탈 수 있다.

처음에 이해를 잘 못 했던 문제이다.😭 그러나 문제만 잘 이해하고나면 어렵지 않게 풀이할 수 있는 문제였다.

🚀 내 풀이

🔥 2 차 풀이 ⭕

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    int result = 0;

    sort(timetable.begin(), timetable.end());
    vector<int> timeTable;
    for (auto& time : timetable)
        timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));

    int index = 0;
    int busTime = 540; // 09:00
    for (int count = 1; count <= n; ++count) {
        int numOfGetOn = 0;
        while (numOfGetOn < m && index < timeTable.size()) {
            if (timeTable[index] <= busTime) {
                numOfGetOn++;
                index++;
            }
            else break;
        }
        
        if (count == n) {
            if (numOfGetOn < m)
                result = busTime;
            else
                result = timeTable[index - 1] - 1;
        }
        busTime += t;
    }
  
    int hours = result / 60;
    if (hours <= 9)
        answer = "0" + to_string(hours) + ":";
    else
        answer = to_string(hours) + ":";

    int minutes = result % 60;
    if (minutes <= 9)
        answer += "0" + to_string(minutes);
    else
        answer += to_string(minutes);

    return answer;
}

버스가 여유 있는지 여부를 따져야 한다.

크루들이 모든 버스에 다 탑승하더라도 콘이 그 뒤에 탈 수 있는 여유가 있다면
- 👉 여유가 있으니 그냥 마지막 버스시간에만 탑승하면 된다. 따라서 마지막 버스 시간에 줄서면 됨.
크루들이 모든 버스에 다 탑승하고나면 콘이 탈 수 있는 여유가 없다면
- 👉 콘은 마지막에 탈 수 있는 크루의 바로 앞에 줄 서야 마지막으로 겨우 탈 수 있다. 즉, 마지막으로 탈 수 있는 크루보다 "1 분" 앞서 줄서면 된다.
  - 예를 들어 버스가 09:00, 09:03 이렇게 2 번 오고 3 명의 정원을 가진다면, [“09:00”, “09:01”, “09:01”, “09:03”, “09:03”] 일 때, 콘은 09:03 에 줄 선 크루보다 더 앞서야지만 버스를 탈 수 있다. 09:03 이 버스를 탈 수 있는 마지노선이기 때문이다. 그러나 콘은 같은 시간에서 맨 뒤에 줄을 서게 되므로 09:03 에 오면 콘은 09:03 에서도 꼴찌기 때문에 탈 수가 없다. 따라서 콘은 크루 대기열의 마지노선인 09:03 보다 1 분 먼저 09:02 에만 오면 된다.

1️⃣ 크루들이 줄서는 시간 비교하기 쉽게 분단위로 변환

    vector<int> timeTable;
    for (auto& time : timetable)
        timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));

문제에서 주어진, 크루들이 줄서는 시간이 “HH:MM” 문자열 형태로 담겨잇는 timetable을 timeTable 벡터를 만들어서 이곳에 분 단위의 int 정수로 변환한다. ‘시’는 60 곱해주고 ‘분’은 그대로.

2️⃣ 버스에 크루들을 태운 후 버스가 여유있는지 없는지를 따져 콘이 줄서야 하는 시간 계산

    int index = 0; // timeTable 의 인덱스 (크루 한명을 가리킴)
    int busTime = 540; // '현재 버스'의 시간. 첫 버스는 무조건 "09:00" (540분)
    for (int count = 1; count <= n; ++count) {  // 버스는 n 번 온다.
        int numOfGetOn = 0; // '현재 버스'에 탄 크루 인원 (m 을 넘어선 안된다.)
        while (numOfGetOn < m && index < timeTable.size()) { // 버스에 태우는 작업
            if (timeTable[index] <= busTime) { // 버스 도착시간 이하에 줄 섰다면 그 크루는 현재 버스에 탈 수 있다.
                numOfGetOn++; // 탑승인원 + 1
                index++; // 다음 크루 검사하러
            }
            else break; // 모든 크루 다 태웠거나 현재 버스 정원 다 찼으면 break. 
        }
        // 모든 버스 다 검사 진행했다면 이제 버스가 여유로웠는지 아닌지 알 수 있다.
        if (count == n) {
            if (numOfGetOn < m) // 마지막 버스의 정원이 다 차지 못했다면 👉 버스 여유 있음 
                result = busTime; // 🤍콘은 마지막 버스 시간에만 오면 된다.
            else if (numOfGetOn >= m) // 마지막 버스의 정원이 다 찼다면 👉 버스 여유 없다.
                result = timeTable[index - 1] - 1; // 🤍콘은 마지막 버스에서 마지막으로 탑승한 사람을 밀어내고 그 사람보다 1분 앞서 타야 한다.
        }

        busTime += t; // 다음 버스 시간으로 업데이트 (다음 버스는 t 분 뒤에 온다.)
    }

while 문을 break 하고난 후의 index는 마지막으로 버스를 탄 크루가 줄 선 시간이다.
- 버스에 여유가 없다면 콘은 이 크루를 제껴 맨 마지막으로 타기위해 1분만 앞서 타면 된다.
최종적으로 result 에 “콘이 줄 서야 하는 마지노선 시간”이 담기게 된다.

3️⃣ 정답으로 구한 콘이 줄 서야 하는 마지노선 시간을 “HH:MM” 문자열로 변환

    /* 시간 HH: */
    int hours = result / 60;
    if (hours <= 9) // 한 자리일 때
        answer = "0" + to_string(hours) + ":";
    else
        answer = to_string(hours) + ":";

    /* 분 MM */
    int minutes = result % 60;
    if (minutes <= 9) // 한 자리일때
        answer += "0" + to_string(minutes);
    else
        answer += to_string(minutes);

    return answer;

🔥 1 차 풀이 ⭕ (But 개선이 필요)

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

using namespace std;

struct Bus {
    int busTime;
    vector<int> people;
};

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";

    vector<int> timeTable;
    for (auto& time : timetable)
        timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));
    sort(timeTable.begin(), timeTable.end());

    vector<Bus> bus;
    int index = 0;
    int busTime = 540; // 09:00
    for (int count = 0; count < n; ++count) {
        vector<int> getOn;
        while (getOn.size() < m && index < timeTable.size()) {
            if (timeTable[index] <= busTime) {
                getOn.push_back(timeTable[index]);
                index++;
            }
            else break;
        }
        bus.push_back({ busTime, getOn });
        busTime += t;
    }

    int hours = 0, minutes = 0;
    if (bus.back().people.size() < m) {
        hours = bus.back().busTime / 60;
        minutes = bus.back().busTime % 60;
    }
    else {
        hours = (bus.back().people.back() - 1) / 60;
        minutes = (bus.back().people.back() - 1) % 60;
    }

    if (hours <= 9)
        answer = "0" + to_string(hours) + ":";
    else
        answer = to_string(hours) + ":";

    if (minutes <= 9)
        answer += "0" + to_string(minutes);
    else
        answer += to_string(minutes);

    return answer;
}

처음에 제출했던 풀이이다. 근데 다 풀고나니 굳이 이렇게 풀 필요가 없겠네 싶었다. 버스에 여유가 없을 땐 마지막 버스에 탄 사람 중에서도 마지막으로 탈 수 있는 사람이 어떤 시간에 줄 섰는지 정보만 있으면 되는데(이 사람 바로 앞에 타면 되니까) 굳이 이렇게 Bus 구조체를 두어 모든 버스들마다 각각 vector로 해당 버스에 탈 수 있는 크루들 정보를 모두 저장할 필요가 전혀 없었다. 그래서 위의 2 차 풀이로, 버스에 다 탈 수 있는 여유가 없을 땐 마지막으로 탈 수 있는 크루의 바로 앞에 탈 수 있도록 고치고 다시 제출했었다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Hyunsang(Harry) Cho 🧸⚽🥩