[알고리즘 풀이 분석] 프로그래머스 셔틀버스 (2018 Kakao Blind Recruitment)

오늘 두번째로 풀어본 문제는 프로그래머스 셔틀버스 이다. 해설처럼 "쉬워보이는데 어려운 문제" 가 맞는 것 같다.
단순한데 시뮬레이션인데 은근히 까다로웠다,,! level 3 맞넹,,
난 이런 문제가 더 어려운 것 같다,,ㅎ

프로그래머스 셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입출력

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45

timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

나의 풀이

특별히 생각나는 알고리즘은 없었고 조건에 맞게 시뮬레이션 하면 되는 문제인 것 같았다. 다만 고려해야 하는 조건이 몇가지 되다 보니 머릿속이 좀 복잡하고 이리저리 헷갈려서 시간이 좀 걸렸던 것 같다.

먼저 버스의 출발 시간, 크루들이 도착하는 시간들 모두 HH:MM 형식의 문자열로 입력되기 때문에 입력되는 timetable 를 모두 분 단위로 계산해서 int 형 배열 crews 에 담아주었고

먼저 온 순서대로 시간 순서대로 태워 보내야 하기 때문에 오름차순으로 정렬하였다.

이후 셔틀버슨는 총 n회 운영되기 때문에 n번의 반복문 안에서 매번 셔틀 버스의 출발 시간에 맞게 최대 m 명을 카운트해주었다.

여기서 항상 유지되는 사실은 콘은 무조건 마지막 셔틀 버스를 타야 한다는 것이다. 하지만 헷갈렸던 것이 m명씩 크루들을 태우면서 콘이 탈 자리가 남아있는 경우와 그렇지 않은 경우에 대한 처리였다.

최대 m 명을 count 해 두고 m명이 다 찼다면 콘은 마지막에 탄 크루보다 1분만 먼저 가면 되고, 그렇지 않다면 콘은 버스 출발 시간에만 도착하면 된다.

콘이 도착해야할 시간을 구했다면 반환 형식에 맞게 변형해서 반환하기만 하면 끝이다!

쓰고보니 역시나,, 별로 어렵지 않은 것 같은데 왜 내머리는 버거워 했던걸까? 알수 없는 알고리즘 풀기 세상 😂

코드

c++

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

// 프로그래머스 셔틀버스, level3, simulation, 2018 kakao blind recruitment
using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> crews;   // 분으로 환산한 크루들의 도착 시간 

    for(int i=0; i<timetable.size(); i++){
        int minute = stoi(timetable[i].substr(0,2)) * 60 + stoi(timetable[i].substr(3,4));
        crews.push_back(minute);
    }
    sort(crews.begin(), crews.end()); // 오름차순 정렬 

    int departure = 540;  // 버스 출발 시간 
    int index = 0; // 현재 제일 앞에 있는 크루 
    int corn_time = 0;  // 콘이 와야하는 시간 

    for (int i = 1; i <= n ; ++i) {  // 총 n대의 셔틀 버스 운행 
        int ride = 0;  // 버스 탄 사람 
        for (int j = index; j < crews.size(); ++j) {
            if (crews[j] > departure) break;
            if (crews[j] <= departure) {  // 셔틀 버스 보다 먼저 온 사람 최대 m 명 태움 
                ride++;
                index++;
                if (ride == m) break;
            }
        }

        if (i==n){  // 마지막 버스라면 콘의 자리가 있을 때 없을 때 도착 시간 계산 
            if (ride == m) corn_time = crews[index-1]-1;
            else corn_time = departure;
        }

        departure += t;
    }

    // 형식 바꿔주기 
    if (corn_time/60 < 10) answer += "0";
    answer += to_string(corn_time/60) + ":";

    if (corn_time%60 < 10) answer += "0";
    answer += to_string(corn_time%60);


    return answer;
}

swift

import Foundation

extension String {
    func substring(from: Int, to: Int) -> String {
        guard from < count, to >= 0, to - from >= 0 else {
            return ""
        }
        
        // Index 값 획득
        let startIndex = index(self.startIndex, offsetBy: from)
        let endIndex = index(self.startIndex, offsetBy: to + 1) // '+1'이 있는 이유: endIndex는 문자열의 마지막 그 다음을 가리키기 때문
        
        // 파싱
        return String(self[startIndex ..< endIndex])
    }
}

func solution(_ n:Int, _ t:Int, _ m:Int, _ timetable:[String]) -> String {
    var crews = [Int]()
    
    for time in timetable {
        let minute = Int(time.substring(from: 0, to: 1))! * 60 + Int(time.substring(from: 3, to: 4))!
        crews.append(minute)
    }
    crews = crews.sorted(by: {$0 < $1})
    
    var departure = 540
    var first = 0
    var corn_departure = 0
    
    for i in 1...n {
        var ride = 0
        for j in first..<crews.count {
            if crews[j] > departure {
                break
            }
            
            if crews[j] <= departure {
                first += 1
                ride += 1
                if ride == m {
                    break
                }
            }
        }
        
        if i == n {
            if ride == m {
                corn_departure = crews[first-1] - 1
            }else{
                corn_departure = departure
            }
        }
        departure += t
    }
    
    var answer = ""
    let hh = corn_departure / 60
    let mm = corn_departure % 60
    
    if hh < 10 {
        answer += "0"
    }
    answer += String(hh) + ":"
    
    if mm < 10 {
        answer += "0"
    }
    answer += String(mm)
    
    return answer
}