카카오 2017 블라인드 테스트 1차: 셔틀버스 (C++)

https://programmers.co.kr/learn/courses/30/lessons/17678

콘이 탈 수 있는 가장 늦은 셔틀버스를 타고 가려면, 몇시에 줄을 서야 하는지를 구하는 문제이다.

다음과 같은 방식으로 생각해 볼 수 있다.

기본적으로 가장 늦은 버스를 탄다는 것은, 막차를 탄다는 것이다. 따라서 막차에 자리가 있으면 그냥 막차를 타면 된다.

막차에 자리가 없는 경우를 생각해보면, 버스를 가장 늦은 시각에 탄 사람보다, 1분 더 빨리 나와서 버스를 타면 탈 수 있는 가장 마지막 순간에 버스를 타게 된다.

동일 시각이라도 콘은 가장 뒤에 줄을 선다고 했기 때문에, 1분 더 빨리 나와서 버스를 타면 되겠다.

위 두가지 경우로 구현을 해주면 되겠다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct Bus {
    int curPop, hour, mint; //버스 현재 인원, 출발 시, 출발 분
};
vector<Bus> bus;
 
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    int hour = 9, minute = 0;
    for (int i = 0; i < n; i++) {
        bus.push_back({ 0, hour, minute });
        minute += t;
        if (minute >= 60) {
            hour++;
            minute -= 60;
        }
    }
    
    sort(timetable.begin(), timetable.end()); 
    //일찍 온 사람부터 나오게 정렬(마지막에 탄사람이 제일 늦게 온 사람인데, 그 사람 찾으려고)
    
    int lastUp = 0; // 마지막에 탄 사람의 인덱스
    for (int i = 0; i < timetable.size(); i++) {
        int hr = stoi(timetable[i].substr(0, 2));
        int mn = stoi(timetable[i].substr(3, 2));
        for (int j = 0; j < bus.size(); j++) {
            if (bus[j].curPop < m && (bus[j].hour > hr || (bus[j].hour == hr && bus[j].mint >= mn))) {
                bus[j].curPop++;
                lastUp = i;
                break; //탈 버스가 정해졌으면 버스 검색 중지
            }
        }
    }
    string hrStr = "";
    string mnStr = "";
    if (bus[bus.size() - 1].curPop < m) { //막차에 자리가 남았다면 막차 시간에 오면 됨
         hrStr = to_string(bus[bus.size() - 1].hour);
         mnStr = to_string(bus[bus.size() - 1].mint);
 
    }
    else { //막차에 자리가 없으면, 마지막에 탄 사람보다 1분 일찍오면 무조건 탈 수 있음
        int lastHr = stoi(timetable[lastUp].substr(0, 2));
        int lastMin = stoi(timetable[lastUp].substr(3, 2));
        lastMin--;
        if (lastMin < 0) {
            lastHr--;
            lastMin += 60;
        }
         hrStr = to_string(lastHr);
         mnStr = to_string(lastMin);
    }
 
    if (hrStr.length() == 1) hrStr = '0' + hrStr;
    if (mnStr.length() == 1) mnStr = '0' + mnStr;
    answer = hrStr + ':' + mnStr;
    
    return answer;
}