[Programmers] [1차] 셔틀버스

콘이 셔틀버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다.

문제해결 전략
우선 콘이 셔틀버스를 최대한 늦게 타기 위해서는 마지막 셔틀버스를 이용하면 된다.

만약 마지막 셔틀버스가 만석이라면 마지막에 탄 사람보다 1분만 먼저오면 무조건 버스를 탈 수 있게 된다.

마지막 셔틀버스가 만석이 아니라면 마지막 셔틀버스의 도착시간에 맞춰 버스를 타면 된다.

위의 세가지 경우를 모두 고려하면 쉽게 구할 수 있는 문제이다.

우선 줄을 선 크루들을 도착 시간 순으로 나열을 한 뒤, 가장 먼저 도착한 인원부터 버스에 태우고 시간을 더해준다. 이 과정을 막차 직전까지만 해 준다.

막차에 대해서는 태울 수 있는 인원-1 만큼만 태우고 나머지 한 자리에 대해서는 빈자리인지, 만석이라면 마지막에 탄 사람이 누구인지 확인하여 위의 조건을 적용해 주 면 된다.

코드

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

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<pair<int,int>> v;
    for(int i=0;i<timetable.size();i++){
        int H = (timetable[i][0] - '0')*10 + timetable[i][1] - '0';
        int M = (timetable[i][3] - '0')*10 + timetable[i][4] - '0';
        v.push_back(make_pair(H,M));
    }
    
    sort(v.begin(), v.end());
    
    int cur = 9*60;
    int idx = 0;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            if(v[idx].first*60 + v[idx].second <= cur){
                idx++;
            }
        }
        cur += t;
    }
    
    for(int i=0;i<m-1;i++){
        if(v[idx].first*60 + v[idx].second <= cur){
            idx++;
            if(idx == v.size())
                break;
        }
    }
    
    int temp = 0;
    if(idx >= v.size()){
        temp = cur;
    }else if(v[idx].first*60 + v[idx].second <= cur){
        temp = v[idx].first*60 + v[idx].second - 1;
    }else{
        temp = cur;
    }
    
    int hh = temp/60;
    int mm = temp%60;
    if(hh < 10)
        answer += '0';
    answer += to_string(temp/60) + ':';
    if(mm < 10)
        answer += '0';
    answer += to_string(temp%60);
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/17678

211006 풀이
정렬 후 앞사람부터 버스 태우면서 만약 이번 버스가 마지막 버스라면 무조건 태워야 한다.

• 꽉찬 마지막 버스인 경우
  마지막 사람보다 1분만 먼저오면 됨
• 여유있는 마지막 버스인 경우
  버스 도착시간 맞춰 도착하면 됨
• 버스에 사람 다탔는데 자리 남은 경우
  버스 도착시간 맞춰 도착하면 됨

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

int change(string t){
    int h1 = t[0] - '0';
    int h2 = t[1] - '0';
    int m1 = t[3] - '0';
    int m2 = t[4] - '0';
    return (h1*10+h2)*60 + m1*10 + m2;
}
string tostring(int t){
    string h = to_string(t/60);
    string m = to_string(t%60);
    if(h.size() == 1)
        h = '0' + h;
    if(m.size() == 1)
        m = '0' + m;
    return h + ':' + m;
}
string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    sort(timetable.begin(), timetable.end());
    int idx = 0;
    int cur = 540;
    int cnt = 0;
    int bus = 0;
    while(1){
        if(idx >= timetable.size())
            break;
        int time = change(timetable[idx]);
        if(time <= cur){
            cnt++;
            idx++;
            if(cnt == m){
                cur += t;
                bus++;
                cnt = 0;
                if(bus == n){
                    answer = tostring(time-1);
                    return answer;
                }
            }
        }else{
            cnt = 0;
            bus++;
            if(bus == n){
                answer = tostring(cur);
                return answer;
            }
            cur += t;
        }
    }
    
    return tostring(cur);
}