프로그래머스 셔틀버스 C++ 문제풀이

Nilo의 개발 일지·2021년 9월 3일

시뮬레이션 알고리즘

알고리즘

목록 보기

16/29

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

아이디어

시뮬레이션을 사용할 줄 안다

접근방식

sort를 사용해서 timetable을 오름차순으로 정리한다

do-while문을 이용, 셔틀을 시간/분으로 나누어서 표기해준다. 분이 60분을 넘을 시, 시로 치환해준다

timetable을 조사하며 만약 셔틀 자리가 남아 있을 시 검사한다

크루가 셔틀 시간안에 오면 타되,
4-1. 만약 셔틀이 꽉차고, 이 차가 막차라면, 내가 못타기에 지금 타는 사람 1분 앞으로 내가 탑승하도록 answer를 저장한다
4-2. 만약 셔틀이 꽉차도 막차가 아니라면, 크루원을 태우고 다음 버스를 기다린다
4-3. 셔틀이 꽉차지 않았다면, 다음 크루로 넘어간다

크루가 재시간에 오지 못하고, 셔틀자리가 남으면 내가 언제든 탈 수 있으니 '셔틀이 오는 시간'에 탑승한다.

만약 셔틀자리가 꽉 차면 다음 셔틀을 위해 자리를 비우고 break 해준다

만약 크루원들 조사가 모두 완료했을 경우, 무조건 셔틀 시간에 탈 수 있기에, 계속 셔틀시간으로 answer를 갱신해준다.

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

using namespace std;

string make_answer(int now_clc,int now_min){
    string s = "";
    if(now_clc >= 10) s += to_string(now_clc);
    else s += "0" + to_string(now_clc);

    s += ":";

    if(now_min >=10) s += to_string(now_min);
    else s += "0" + to_string(now_min);

    return s;
}

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

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

    int shut_clc = 9; // 셔틀 시
    int shut_min = 0; // 셔틀 분
    int how_many = 0;
    int i = 0;
    int now_pos = 0;
    do{

        //timetable을 계속 찾음
        while(now_pos < timetable.size()){
            int now_clc = stoi(timetable[now_pos].substr(0,2));
            int now_min = stoi(timetable[now_pos].substr(3,2));

            //만약 셔틀자리가 남으면, 검사
            if(how_many < m){
                //만약 크루가 셔틀 안에 오면 탐
                if(now_clc < shut_clc || (now_clc == shut_clc && now_min <= shut_min)){
                    how_many++;
                    if(how_many == m && i +1 == n){ //만약 셔틀 꽉차면? -> 내가 못탐, 지금 놈 1분 앞으로 탐
                        if(now_min == 0) answer = make_answer(now_clc-1,59);
                        else answer = make_answer(now_clc,now_min-1);
                        break;
                    }
                    else if(how_many == m && i + 1 < n) { //막차가 아니다? -> 태우고 다음 버스 기다림
                        how_many = 0;
                        now_pos++;
                        break;
                    }
                    else{ //크루가 타면? 다음 크루로 넘어감
                        now_pos++;
                    }
                }
                //그게 아니면? 내가 탈 수 있음 -> 셔틀 올때 바로 탐
                else{
                    answer = make_answer(shut_clc,shut_min);
                    how_many = 0;
                    break;
                }
            }

            //만약 셔틀자리가 꽉차면? -> 다음 셔틀 위해 자리 비움, break
            else if(how_many == m) {
                    how_many = 0;
                    break;
                }
        }

        if(now_pos == timetable.size()) { // 크루들 신경 쓸 필요 X -> 무조건 셔틀시간
            answer = make_answer(shut_clc,shut_min);
        }

        i++;
        shut_min+=t;
        if(shut_min >= 60){
            shut_clc++;
            shut_min-=60;
        }

    }while(i<n);

    return answer;
}