[2018 카카오 블라인드 공채] 셔틀버스 (C++)

2018 카카오 블라인드 공채 1차 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - [1차] 셔틀버스 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - [1차] 셔틀버스

---

5번 문제였으며 1시간 30분 정도 소요되었다.

가장 시간이 많이 걸렸던 문제였으며, 많이 꼬였던 문제다.

제일 처음, 시간을 빨리온 순서대로 sort해야하는데 C++의 문자열 sorting에 대해 정확히 알지 못해 꼬일수도 있다 판단하여 int로 변경한 후, 내림차순으로 sorting 해 주었다.

그 후, 탈 수 있는 인원과 막차 시간을 계산하여 반복문 없이 조건과 값을 이용해 풀 수 있을 줄 알았다.

여기에 갖다버린 시간이 족히 30분은 될것이다.

하지만 그렇게 풀려니 계산도 복잡하고 되는지 안되는지도 모르겠어서 그냥 simulation형태로 반복해주며 진행해주었다.

FIFO형태로 풀었으며, 마지막 버스 전까지는 모든 버스에 탈 수 있는 최대한의 인원을 태우고, 마지막 버스에서는  자신이 타야하기 때문에 한자리를 남기고 태워야 한다.

그렇기 때문에 마지막 사람을 태우고 남은 인원중에 제일 앞에 있는 사람보다 빨리 오면 된다. (제일 앞에 있는 사람 시간 - 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> time;

    for (int i = 0; i < timetable.size(); i++)
    {
        string H = timetable[i].substr(0, 2);
        string M = timetable[i].substr(3, 2);

        time.push_back(stoi(H) * 60 + stoi(M));
    }

    sort(time.begin(), time.end());

    int last = 9 * 60 + t * (n - 1);
    int limit_num = m * n;

    int cnt = 0;
    int flag = 0;
    int temp;
    
    int start = 9 * 60;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (time.empty())
                break;

            if (time[0] <= start)
                time.erase(time.begin());
            else
                break;
        }
        start += t;
    }

    for (int j = 0; j < m - 1; j++)
    {
        if (time.empty())
            break;

        if (time[0] <= start)
            time.erase(time.begin());
        else
            break;
    }

    if (time.empty())
        temp = last;
    else
    {
        if (time[0] <= last)
            temp = time[0] - 1;
        else
            temp = last;
    }

    int H = temp / 60;
    int M = temp % 60;

    if (H < 10)
        answer += "0";
    answer += to_string(H);
    answer += ":";
    if (M < 10)
        answer += "0";
    answer += to_string(M);

    return answer;
}