2018 KAKAO BLIND RECRUITMENT[1차] 셔틀버스 (C++)

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

프로그래머스

 

문자열로 표현된 시간을 계산하는 것이 조금까다로웠던 문제 오히려 자바로 풀이했다면 조금 더 쉬웠을 것 같다.

 

알고리즘은 다음과 같다. 

1. 크루들이 도착하는 시간을 정렬한다.

2.가장 처음 버스 시간대인 9:00 부터 크루들이 도착하는 시간과 비교한다.

 2-1. 만약 지금 버스 시간대보다 일찍 왔다면 레디큐에 넣는다. 

 2-2. 레디큐의 크기가 버스의 최대 승객이라면 레디큐를 비우고 다음 시간대의 버스 시간대와 비교시킨다.

 2-3. 만약 지금 버스 시간대보다 늦게 왔다면 지금 승객이 탈 수 있는 버스가 올 때 까지 버스 시간을 조정한다.

 

2번을 계속 반복하는데 단, 버스의 개수를 초과하면 break 시킨다.

 

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

bool timeCompare(string a, string b){ // a가 빠르면 true, b가 빠르면 false 
    string a_o = "";
    string b_o = "";
    string a_m = "";
    string b_m = "";
    
    a_o.push_back(a[0]);
    a_o.push_back(a[1]);
    a_m.push_back(a[3]);
    a_m.push_back(a[4]);
    
    b_o.push_back(b[0]);
    b_o.push_back(b[1]);
    b_m.push_back(b[3]);
    b_m.push_back(b[4]);
    
    int a_our = stoi(a_o);
    int b_our = stoi(b_o);
    int a_min = stoi(a_m);
    int b_min = stoi(b_m);
    
    if(a_our == b_our) return a_min <= b_min;
    else return a_our < b_our;
}

string timeSub(string a, int b){
     string a_o = "";
    string a_m = "";
    
    a_o.push_back(a[0]);
    a_o.push_back(a[1]);
    a_m.push_back(a[3]);
    a_m.push_back(a[4]);
    
    int a_our = stoi(a_o);
    int a_min = stoi(a_m);
    
    a_min--;
    
    if(a_min < 0){
        a_our--;
        a_min = 59;
    }
    
    string res_a_our = to_string(a_our);
    string res_a_min = to_string(a_min);
    
    if(res_a_our.size() == 1) res_a_our = "0" + res_a_our;
    if(res_a_min.size() == 1) res_a_min = "0" + res_a_min;
    
    return res_a_our + ":" + res_a_min;
}

string timeAdd(string a, int b){
    string a_o = "";
    string a_m = "";
    
    a_o.push_back(a[0]);
    a_o.push_back(a[1]);
    a_m.push_back(a[3]);
    a_m.push_back(a[4]);
    
    int a_our = stoi(a_o);
    int a_min = stoi(a_m);
    
    a_our += (a_min + b) / 60;
    a_min = (a_min + b) % 60;
    
    string res_a_our = to_string(a_our);
    string res_a_min = to_string(a_min);
    
    if(res_a_our.size() == 1) res_a_our = "0" + res_a_our;
    if(res_a_min.size() == 1) res_a_min = "0" + res_a_min;
    return res_a_our + ":" + res_a_min;
}

string solution(int n, int t, int m, vector<string> timetable) {    
    sort(timetable.begin(), timetable.end());
        
    string busTime = "09:00";
    
    vector<string> readyQueue;
    int busCnt = 1;
    for(int i = 0; i < timetable.size(); i++){
        string now = timetable[i];
        if(timeCompare(now, busTime)){ // 이번 버스를 탈 수 있는 시간에 옴
            readyQueue.push_back(now); // 버스 탑승 가능 큐에 담김
            if(readyQueue.size() == m) { // 버스 최대 인원 도달
                busCnt++;
                if(busCnt > n) break;
                busTime = timeAdd(busTime, t); // 다음 버스 타임 설정
                readyQueue.clear();        
            }
        }else{ // 버스를 탈 수 없는 시간에 옴
            readyQueue.clear();
            
            while(busCnt < n){
                busTime = timeAdd(busTime, t);
                busCnt++;
                if(timeCompare(now, busTime)){
                    readyQueue.push_back(now);
                    
                    break;
                }
            }
            
        }
    }
    
    if(readyQueue.size() == m){
        string lastTime = readyQueue[readyQueue.size() - 1];
        
        return timeSub(lastTime, -1);
    }else {
        return busTime;
    }
}