프로그래머스 - [1차] 셔틀버스 [C++]

 이 문제는 구현 문제인 것 같다. 이 문제에서 중요한 것은 어떤 걸 중심으로 잡아서 구현할지이다. 나는 처음에 시간을 중심으로 반복문을 돌려서 문제를 풀었는데, 이렇게 풀면 풀이가 어려워지고 오답이 나올 가능성이 높다. 그래서 검색을 한 결과 버스를 기준으로 반복문을 돌리면 굉장히 풀이가 직관적이고 쉽게 나오게 된다.

 

 처음에 버스가 도착하는 시간을 계산하여 벡터에 넣고, 이에 대해 반복문을 돌리면서 해당 버스에 탈 수 있는 인원을 체크한다. 그 인원이 한 버스 당 최대 인원보다 적으면 버스가 오는 시간 정각에 가는게 가장 늦게 탈 수 있고, 그렇지 않으면 마지막 인원보다 1분 더 일찍 와야 해당 버스를 탈 수 있다. 

 

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

using namespace std;

vector<string> split(string input, char delimit) {
    stringstream ss(input);
    string temp;
    vector<string> result;
   
    while (getline(ss, temp, delimit)) {
        result.push_back(temp);
    }
    
    return result;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    
    vector<pair<int, int>> table;
    
    // 입력 배열 초기화
    for (string& tt : timetable) {
        vector<string> temp = split(tt, ':');
        
        int hour = stoi(temp[0]);
        int min = stoi(temp[1]);
        
        table.push_back({hour, min});
    }
    
    sort(table.begin(), table.end());
    
    // bus 초기화
    vector<pair<int, int>> bus;
    
    bus.push_back({9, 0});
    
    n--;
    
    int initHour = 9;
    int initMin = 0;
    for (int i = 0; i < n; i++) {
        initMin += t;
        
        if (initMin >= 60) {
            initHour += initMin / 60;
            initMin %= 60;
        }
        
        bus.push_back({initHour, initMin});
    }
    
    pair<int, int> tempAnswer;
    
    int idx = 0;
    for (int i = 0; i < bus.size(); i++) {
        pair<int, int> present = bus[i];
        int cnt = 0;
        pair<int, int> last = present;
        
        // 해당 버스에 탈 수 있는 인원들
        while (idx < table.size()) {
            if (table[idx].first > present.first) {
                break;
            }
            
            if (table[idx].first == present.first && table[idx].second > present.second) {
                break;
            }
            
            if (cnt == m) {
                break;
            }
            
            last = table[idx];
            cnt++;
            idx++;
        }
        
        if (cnt < m) {
            tempAnswer = present;
        }
        else {
            tempAnswer = last;
            tempAnswer.second--;
            
            if (tempAnswer.second == -1) {
                tempAnswer.first--;
                tempAnswer.second = 59;
            }
        }
    }
    
    string hour = to_string(tempAnswer.first);
    
    if (hour.size() == 1) {
        hour = '0' + hour;
    }
    
    string min = to_string(tempAnswer.second);
    
    if (min.size() == 1) {
        min = '0' + min;
    }
    
    answer += hour;
    answer += ':';
    answer += min;
    
    return answer;
}