[프로그래머스/알고리즘] 셔틀버스

셔틀버스

입출력 예제

n = 1;

t = 1;

m = 5;

timetable = { "08:00", "08:01", "08:02", "08:03" };

return : "09:00"

해결 방법

이 문제는 콘이라는 사람이 막차를 타고 가장 늦게 타는 것이 핵심입니다.

처음에 timetable의 시간은 제각각이라서 우선순위 큐를 이용해서 정렬해줬습니다.

막차가 아니면 그 시간대의 사람은 전부 태울 수 있고 막차가 아닌데 그 시간대에 탈 수 있는 사람이 없다면 태울 수 있는 사람만 태우고 가버리면 되고 막차이든 막차가 아니든 사람이 없으면 가장 마지막 배차를 반환해 줘야 합니다. 그리고 막차인데 태울 수 있는 한도가 많을 경우 가장 마지막번째의 타는 사람보다 1분 도착하도록 반환을 해주는 것으로 풀었습니다. 

정말 무식하게 풀었던 문제였습니다.

소스코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <functional>
using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
	string answer = "";
	int lastbus = n;
	int currentbus = 1;
	int start_time = 540;		//9시 
	int result = 0;

	priority_queue<int, deque<int>, greater<int>> int_time;
	
	for (int i = 0; i < timetable.size(); i++) {
		string hour;
		string minute;
		hour += timetable[i][0];
		hour += timetable[i][1];
		minute += timetable[i][3];
		minute += timetable[i][4];
		int_time.push(stoi(hour) * 60 + stoi(minute));
	}

	int i=0;
	while (currentbus <= lastbus) {		
		if (!int_time.empty()){
			if (int_time.top() <= start_time) {
				if (i == m - 1 && currentbus == lastbus) {
					result = int_time.top() - 1;
					break;
				}
				int_time.pop();
				i++;
			}
			else {
                                if (currentbus == lastbus) {
					result = 540 + t*(n - 1);
					break;
				}
				currentbus++;
				start_time += t;
				i = 0;
				continue;
			}
		}
		else {		//사람이 없다.
			result = 540 + t*(n - 1);
			break;
		}

		if (i == m) {
			currentbus++;
			start_time += t;
			i = 0;
		}
	}

	if (result / 60 >= 10) {		//시
		answer += to_string(result / 60);
		answer += ":";
	}
	else {
		answer += "0";
		answer += to_string(result / 60);
		answer += ":";
	}

	if (result % 60 >= 10) {		//분
		answer += to_string(result % 60);
	}
	else {
		answer += "0";
		answer += to_string(result % 60);
	}
	
	return answer;
	
}