[PriorityQueue] (프로그래머스 Lv 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 사이
• 출력: 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각

n	t	m	timetable	result
1	1	5	["08:00", "08:01", "08:02", "08:03"]	"09:00"
2	10	2	["09:10", "09:09", "08:00"]	"09:09"
2	1	2	["09:00", "09:00", "09:00", "09:00"]	"08:59"
1	1	5	["00:01", "00:01", "00:01", "00:01", "00:01"]	"00:00"
1	1	1	["23:59"]	"09:00"
10	60	45	["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]	"18:00"

풀이

• 마지막 차 시간에 m보다 적게 탄다면 마지막 차 출발 시각이 정답이 되고, 마지막 차 시간에 m 이상 탄다면 마지막 탑승자의 도착 시각보다 1분 일찍 와있어야 함.
• 시간을 모두 분 단위로 바꿔서 우선순위 큐에 삽입
• 9:00 부터 t분 간격으로 n-1회 루핑을 돌면서 대기열에 시간들 중 현재 시간 이하의 도착 시각들을 빼낸다.
• 마지막 차일 때 탑승가능한 사람 수를 구함
  • m명 이상이면 timetable의 m번째 도착 시간 - 1 을 반환
  • m명보다 작으면 마지막 차의 시각을 반환
• 정답 코드

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    // 모든 시간을 분 단위로 바꿔서 우선순위 큐에 삽입
    priority_queue<int> pq;
    for (auto& s : timetable) {
        int minutes = ((s[0]-'0')*10 + (s[1]-'0')) * 60 + (s[3]-'0')*10 + (s[4]-'0');
        pq.push(-minutes); // 큰 값이 맨 위에 오기 때문에 -1을 곱해서 작은 값이 오도록 함
    }
    
    // 마지막 차 시간이 올 때까지 우선순위 큐에서 탑승가능한 사람들을 빼냄
    int busTime = 9*60;
    for (int i = 0; i < n-1; i++, busTime += t)
        for (int j = 0; j < m; j++)
            if (pq.empty() or -pq.top() > busTime) break;
            else pq.pop();
    
    // 마지막 차 시간에 마지막으로 탑승하는 사람의 도착 시각 - 1 구하기
    int arrivalTime;
    while (!pq.empty() and m) {
        if (-pq.top() <= busTime) {
            arrivalTime = -pq.top() - 1;
            pq.pop();
            m--;
        } else break;
    }
    
    if (m > 0) arrivalTime = busTime; // 막차에 자리가 있으면 버스 도착 시각으로 변경
    char tmp[6];
    sprintf(tmp, "%02d:%02d", arrivalTime / 60, arrivalTime % 60);
    return string(tmp);
}