[programmers] [1차] 셔틀버스

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

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

구현

 

---------------------------------------------------풀이----------------------------------------------------

 

우선, timetable을 오름차순 정렬한다.

이제부터 크루들의 번호는 timetable에서의 인덱스를 의미한다.

 

시간은 비교의 편의를 위해 '시간*60+분'이라는 하나의 숫자로 표현하였다.

cur_bus는 현재 셔틀 시간을 의미하고,(9시에 첫차이므로 cur_bus=9*60)

waiting은 바로 다음에 도착할 사람을 의미한다.

cur_in은 현재 셔틀에 탄 사람 수이다.

 

for문을 돌려, 총 셔틀 수 n만큼 체크하였다.

맨 처음에는, 셔틀에 탄 사람이 0명이도록 cur_in을 초기화한다.

그 다음, while문에서 셔틀에 탄 사람이 m명을 채워 더 탈 수 없거나(cur_in >= m),

다음 도착할 사람이 현재 셔틀 시간 다음에 도착하면(timetable[waiting] > cur_bus)

종료한다.

그 전까지는 사람을 셔틀에 한 명씩 태우는 과정(waiting++, cur_in++)을 진행한다.

while문이 종료하면, 다음 셔틀을 운행(cur_bus += t)한다.

 

이렇게 for문이 끝나면(모든 셔틀 운행이 끝나면)

최종 셔틀 시간을 가져오기 위해 cur_bus -= t를 해준다. -> 마지막 셔틀 시간이 중요하기 때문. 그게 가장 늦을 수 있는 시간이므로.

 

이제, 뒤에 미래에 도착할 크루(waiting)가 있을 경우와 없을 경우로 나누어준다.(모든 사람이 셔틀에 탄 경우와 아닌 경우)

waiting은 현재 다음 도착할 사람 번호를 가리킬 것이다.

먼저, waiting이 없을 경우(waiting == 총 크루 수), -> 다음 도착할 사람이 없거나 마지막 셔틀 시간 뒤에 온다는 것.

-> 모든 크루가 셔틀에 탔다는 의미. -> 마지막 셔틀을 기준으로 셔틀이 가득찼는지 아닌지 보면 된다.

셔틀이 가득차지 않아 탈 수 있으면(cur_in < m), 그냥 그 셔틀 시간에 도착하면 된다. 따라서 answer = cur_bus(최종셔틀시간)

가득찼다면, 가장 늦게 셔틀에 탄 사람보다 1분 먼저 도착하면 된다. answer = timetable[waiting-1] - 1

 

waiting이 있을 경우, -> 다음 도착할 사람이 있다는 것. -> 모든 크루가 셔틀에 타지 못했다. -> 마지막으로 탄 사람보다 빨라야함.

셔틀이 가득찼으면(cur_in == m),

셔틀에 마지막으로 탄 사람보다 1분 빠르게 도착해야 한다. answer = timetable[waiting-1] - 1

아니라면 최종 셔틀 시간과 waiting의 시간-1분 중 작은 값을 선택한다. answer = min(cur_bus, timetable[waiting]-1)

이렇게 하는 이유는,

최종 셔틀만 고려할 경우 예외가 발생하기 때문이다.

예를 들어, 셔틀이 하나만 운행하는데

크루가 6시, 7시, 8시에 도착한다고 하자.

한 명만 탈 수 있다면, 셔틀은 9시에 운행하므로 6시에 온 사람이 탈 것이고,

셔틀만 고려해 8시59분에 온다면 7,8시에 온 사람이 우선순위를 갖게 된다.

즉, 셔틀이 왔는데 이미 많은 사람이 기다리면, 그 앞에서 기다려야만 한다.

또, 크루가 8시,11시에 도착한다고 하자.

셔틀은 8시에 온 사람이 탈 것이고,

크루만 고려해 10시 59분에 온다면 셔틀을 탈 수 없다. 이 경우, 그 누구도 셔틀을 탈 수 없게 된다.

셔틀 시간보다는 작아야 탈 기회를 얻을 수 있고, 그때 탈 크루보다 먼저 도착해야 탈 수 있다는 것이다.

 

이 로직을 구현하는 과정에서 편의에 따라 time string을 int로, 혹은 time int를 string으로 바꾸는 함수를 만들어 진행하였다.

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

using namespace std;

// s~e-1까지를 int로 반환
int str_to_int(string time, int s, int e){
    int ret = 0;
    for(int i = s; i < e; i++){
        ret = ret*10 + (time[i]-'0');
    }
    return ret;
}

// 시간을 분단위로 표현. 시*60+분
int time_to_int(string time){
    return str_to_int(time, 0, 2)*60 + str_to_int(time, 3,5);
}

string time_to_str(int time){
    string ret = "";
    int hour = time/60;
    int min = time % 60;
    ret += hour/10 + '0';
    ret += hour%10 + '0';
    ret += ":";
    ret += min/10+'0';
    ret += min%10+'0';
    return ret;
}

// 9시부터 n회, t분 간격으로 역에 도착. 최대 m명.
// 도착한 시간에 대기열에 선 크루까지 대기 순서대로 태움.
// 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 앎.
// 셔틀 타고 사무실로 갈 수 있는 도착시간 중 제일 늦은 시각=?
// 같은 시간에 도착한 크루 중 대기열 제일 뒤에 선다.
// 00:01~23:59
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    // 앞시간부터로 정렬
    sort(timetable.begin(), timetable.end());
    
    int cur_bus = 9*60; // 현재 셔틀 시간->9시에 시작
    int waiting = 0;    // 대기하는 사람 맨처음 번호 - sorting한 timetable 기준
    int cur_in = 0; // 현재 탄 사람 수
    // 셔틀 수만큼 돌 것임.
    for(int i = 0; i < n; i++){
        // 사람 수(m)를 다 채우거나
        // 셔틀 시간을 넘어가기 전까지 태움.
        // 그 마지막 사람 기억하기.
        cur_in = 0;
        while(waiting < timetable.size()){
            // 사람 태울 수 없으면 종료
            if(cur_in >= m 
               || time_to_int(timetable[waiting]) > cur_bus){
                break;
            }
            waiting++;
            cur_in++;
        }
        cur_bus += t;
    }
    cur_bus -= t;   // 최종 셔틀 시간
    
    // waiting이 없을 경우
    if(waiting >= timetable.size()){
        // 그냥 더 탈 수 있으면
        if(cur_in < m){
            // 마지막 셔틀 시간에 타면 됨.
            answer = time_to_str(cur_bus);
        }
        // 더 탈 수 없으면 가장 늦게 탄 사람보다 1분 먼저 대기
        else{
            answer = time_to_str(time_to_int(timetable[waiting-1])-1);
        }
    }
    // waiting이 있을 경우 -> 최종 셔틀까지 못탔다는것!
    else{
        // 직전에 탄 사람이 m명을 채우는거였으면
        if(cur_in == m){
            // 그 사람보다 1분 먼저
            answer = time_to_str(time_to_int(timetable[waiting-1])-1);
        }
        // 아니면 최종 셔틀 시간과 (마지막 waiting-1) 중 작은값에 타면 됨.
        else{
            answer = time_to_str(min(cur_bus, time_to_int(timetable[waiting])-1));
        }
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

분명 다 풀었는데 왜 틀렸는지 고민한 문제..

질문하기에서 테스트케이스를 공유해주신 어떤 감사한 분 덕분에 찾았다.

사실상 오타?....

waiting이 있을 경우, 직전에 탄 사람이 m명을 채우는거였으면,

그 사람보다 1분 먼저 도착해야 하므로,

timetable[waiting-1]을 가져와야하는데 timetable[waiting]이라고 써놔서...ㅠㅠㅠ

별거아닌데 이거 못찾아서 오래걸린 문제!