[C++] 프로그래머스 셔틀버스 풀이

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

코딩테스트 연습 - [1차] 셔틀버스

이 문제는 조건을 차근차근 맞춰나가면 충분히 풀 수 있는 문제이다. 핵심은 버스의 수, 버스 1대당 탈 수 있는 인원의 수를 생각해야한다는 점이다. 시간관련 문제를 풀 때 모든 시간을 가장 작은 단위로 통일하는 것이 굉장히 편하다. 이 문제에서는 가장 작은 단위가 분이므로 모든 시간을 몇분인지 계산하면 쉽게 구할 수 있다. 특히 소수점이 나오는 시간문제는 부동 소수점으로 계산할 경우 계산 과정에서 원하는 값이 나오지 않을 수 있으므로 integer형으로 계산하는 것이 가장 좋다. 코드는 다음과 같다.

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

using namespace std;

bool cmp(string a, string b) { //내림차순 정렬
    return a > b;
}

int part(string a) { //string을 시간으로 변경
    pair<int,int> hm;
    hm.first = stoi(a.substr(0, 2)); //hour 분리
    hm.second = stoi(a.substr(3, 2)); //minute 분리
    int ret = hm.first * 60; //분으로 합치기
    ret += hm.second;
    return ret;
}

string timetostring(int time) { //시간을 string으로 변경
    string ret = "";
    int h = time / 60; //hour 분리
    int m = time % 60; //minute 분리
    if(h < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(h);
    ret += ':';
    if(m < 10) //1자리 수인 경우 앞에 '0' 붙이기
        ret += '0';
    ret += to_string(m);
    return ret;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    sort(timetable.begin(), timetable.end(), cmp); //내림차순으로 정렬
    int now = 540; //9시 정각
    int end = now + (t * (n-1)); //버스 마지막 시간
    int cnt = 0; //마지막 버스 탑승자 카운트
    for(int i = 0; i < n; i++) { //n개의 버스
        if(i == n - 1) { //마지막 버스일 경우
            if(cnt == m - 1) break; //1자리 남은 경우 break
        }
        if(timetable.empty()) break; //모두 탄 경우 break
        for(int j = 0; j < m; j++) { //m개의 탑승자 수 만큼
            if(timetable.empty()) break; //모두 탄 경우 break
            int hm = part(timetable.back()); //가장 빨리온 사람 시간으로 변경
            if(hm <= now) { //현재 버스를 탈 수 있는 경우
                timetable.pop_back(); //버스에 탑승
                if(i == n - 1) { //마지막 버스인 경우
                    cnt++; //탑승자 수 증가
                    if(cnt == m-1) break; //마지막 버스 1자리 남은 경우 break
                }
            }
            else { //가장 빨리온사람도 현재 버스를 탈 수 없는 경우 break
                break;
            }
        }
        now += t; //다음 버스
    }
    if(timetable.empty()) { //모두 버스에 타고도 자리가 남은 경우
        answer = timetostring(end); //마지막 버스 탑승
    }
    else {
        int back = part(timetable.back()); //남은 탑승자 중에 가장 빠른 사람
        if(back > end) { //마지막 버스보다 뒤에 오는 경우
            answer = timetostring(end); //콘은 마지막 버스 탑승
        }
        else { //남은 탐승자 중에 가장 빠른 사람이 버스를 탈 수 있는 경우
            back--; //콘은 1분 일찍 도착해서 버스 탑승
            answer = timetostring(back);
        }
    }
    return answer;
}

이 문제에서 중요한 것은 마지막 버스이다. 마지막 버스에 자리가 있는지 없는지를 판단하는 것이다. 각 버스에 최대 m명을 태울 수 있으므로 버스가 오는 시간까지 기다리고 있는 사람은 버스에 태워 보낸다. m명이 모두 차지 않더라도 정류장에 도착한 사람이 없는 경우 버스는 출발한다. 마지막 버스가 도착했을 때 m-1명까지만 버스에 태운다. 마지막 1자리는 콘이 타야하기 때문이다. 그리고 프로그램 마지막에 판단한다. 이때 경우의 수가 3가지가 있다.

 

    1. 만약 정류장에 기다리는 사람이 없는 경우 콘은 마지막 버스가 출발하는 시간에 도착하면 된다.

    2. 만약 정류장에 사람이 기다리고 있지만 그 사람은 마지막 버스가 출발하는 시간보다 늦게 오는 경우 1번과 마찬가지로 마지막 버스의 시간과 같으면 된다.

    3. 마지막으로 남은 탑승자가 마지막 버스가 출발하는 시간보다 먼저 와서 기다리는 경우 그 사람보다 1분 먼저 도착하면 된다. 그렇다면 가장 높은 우선순위이기 때문에 마지막 1자리를 탈 수 있다.

 

이렇게 버스는 n개, 버스 하나 당 m명 탑승 가능이라는 조건을 하나하나 맞춰 나가고 마지막 1자리를 콘이 탈 수 있는 조건으로 위의 3가지 경우만 생각할 경우 문제를 쉽게 풀 수 있다. 이 문제의 핵심은 string으로 주어진 시간을 integer형으로 바꾸어 계산을 편하게 한 점과 조건을 하나하나 맞춰 경우의 수를 나누어 풀은 부분이라고 생각한다.