2018 - [1차] 셔틀버스

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

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

[ 문제풀이 ]

이번 문제도 시간을 초로 환산하는 방법을 알고 있으면 수월하게 해결할 수 있는 문제이다.

​주어진 조건을 잘 읽어보면 결국 정답이 될 수 있는 케이스는 마지막 버스일 경우에 승객을 태울 수 있는지에 대한 여부이다.

​마지막 버스일 경우 현재 버스가 아직 승객을 태울 수 있다면 현재 버스의 시간이 정답이고 태울 수 없다면 마지막으로 탑승한 승객보다 1분 빠른 시간이 정답이다.

​하지만 잘 생각해 보면 탑승할 승객이 더 이상 존재하지 않는다면 굳이 마지막 버스까지 확인할 필요가 없다. 더 이상 승객이 없다면 제일 마지막 버스의 시간이 정답이기 때문이다.

import java.util.*;

class Solution {
	public String solution(int n, int t, int m, String[] timetable) {
		PriorityQueue<Integer> passenger_List = new PriorityQueue<>();

		for (String s : timetable) {
			String[] str = s.split(":");
			int time = Integer.parseInt(str[0]) * 60 + Integer.parseInt(str[1]);

			passenger_List.offer(time);
		}

		int answer = 0;
		int startTime = 540; //버스 시작시간 09:00

		//모든 버스를 돌면서
		for (int i = 1; i <= n; ++i) {
			int lastTime = 0; //마지막 승객 시간
			int isValid = m;  //버스가 수용가능한 승객의 수

			while (!passenger_List.isEmpty()) {
				//승객을 태울 수 있으면
				if (passenger_List.peek() <= startTime && isValid > 0) {
					lastTime = passenger_List.poll();
					isValid--;
					continue;
				}

				break;
			}

			//마지막 버스일 경우
			//승객을 아직 태울 수 있으면 현재 버스의 시간
			//승객을 더이상 태울 수 없으면 마지막 승객보다 1분 앞
			if (i == n) {
				answer = isValid == 0 ? lastTime - 1 : startTime;
				break;
			} 
			//마지막 버스가 아닐 경우
			else {
				//더이상 태울 승객이 없으면 마지막 버스 시간
				if (passenger_List.isEmpty()) {
					answer = startTime + (n - i) * t;
					break;
				}

				//다음 버스 시간
				startTime += t;
			}
		}

		return String.format("%02d:%02d", answer / 60, answer % 60);
	}
}