프로그래머스 - 셔틀버스(Java)

구현 문제입니다.

 

버스의 정보와 크루들의 정보가 주어질 때, 콘이 버스를 탈 수 있는 최대 시간을 구하는 문제입니다.

즉, 콘은 마지막 버스를 타게 됩니다.

 

1.

09:00에 도착하는 한 대가 있습니다.

timetable의 인원이 m보다 작기 때문에 09:00에 도착하면 됩니다.

 

2.

09:00, 09:10에 도착 및 출발하는 두 대가 있습니다.

08:00에 도착하는 크루가 09:00차를 혼자타게 됩니다.

이후 버스인 09:10 버스는 수용 인원이 두 명이기 때문에, 콘은 제일 늦은 사람인 09:10보다 1분 일찍 와야합니다.

때문에 09:09에 도착해야 합니다.

 

3.

09:00, 09:01에 도착 및 출발하는 두 대가 있습니다.

먼저 09:00에 2명이 먼저 출발합니다.

이후 마지막 버스 도착 시간인 09:01에 오면 앞 선 두명이 타게 되므로, 08:59분에 와야합니다.

 

4.

09:00에 도착 및 출발하는 한 대가 있습니다.

크루의 수가 버스의 최대 수용 인원 이상이고, 가장 늦게도착하는 크루인 00:01보다 1분 빨리 와야 합니다.

즉, 00:00에 와야합니다.

 

5.

09:00에 도착 및 출발하는 한 대가 있습니다.

문제 조건에 의해, 23:59분에 일괄적으로 전부 집에 들어갑니다.

때문에 콘은마지막 버스인  09:00에 와서 탈 수 있습니다.

 

6.

09:00 부터 18:00까지 한 시간 간격으로 도착하는 버스가 열 대가 있습니다.

문제 조건에 의해, 23:59분에 일괄적으로 전부 집에 들어갑니다.

때문에 콘은마지막 버스인  18:00에 와서 탈 수 있습니다.

 

구현할 때 주의점이 있습니다.

막차 시간을 기준으로 정류소 마지막 크루 시간의 -1을 하면 안됩니다.

정류소에 언제 크루 및 버스가 도착하느냐에 따라, 정류소의 인원을 감소시키는 방법이 달라집니다.

예시를 보겠습니다.

n = 10
t = 25
m = 1
timetable = {"09:00", "09:10", "09:20", "09:30", "09:40", "09:50",
        "10:00", "10:10", "10:20", "10:30", "10:40", "10:50"}

마지막 버스가 도착하는 시간은 (n-1)*t + "09:00"입니다.

즉, 예시의 마지막 버스의 시간는 10시 50분 이지만 버스를 탑승하는 마지막 크루의 정류소 도착 시간은 10시 30분 입니다.

 

저는 처음에 마지막 버스의 시간만을 고려하여 -1을 했지만, 위의 예시 처럼 크루인원이 스택처럼 쌓일 수 있는 경우를 고려해야 합니다.

 

[구현 코드]

import java.util.*;

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

        // 첫차
        int firstBus = hourToMinutes("09:00");

        // 마지막 셔틀 도착 시간
        int lastBus = (n - 1) * (t) + firstBus;

        // 셔틀 버스에 탈 수 있는 사람을 추가함
        // 마지막 버스 이후~23:59분 까지 도착 인원을 추가하지 않음
        for (String table : timetable) {
            int arrive = hourToMinutes(table);
            if (arrive <= lastBus) pq.add(hourToMinutes(table));
        }

        int corn = 0;
        // 마지막 버스 전 까지 사람을 태워서 보냄
        for (int i = 0; i < n - 1; i++) {
            int bus = (i * t) + firstBus;
            for (int j = 0; j < m; j++) {
                if (!pq.isEmpty()) {
                    int person = pq.poll();
                    if (person > bus) {
                        pq.add(person);
                        break;
                    }
                }
            }
        }

        // 마지막 버스일 때, 콘의 최대 도착 시간을 구함
        if (pq.isEmpty()) corn = lastBus;
        else {
            // 마지막 버스 탑승 제한인원보다 정류장 인원이 많거나 같을 때
            if (pq.size() >= m) {
                for(int i=0; i<m; i++){
                    if(!pq.isEmpty()) corn = pq.poll();
                }
                corn--;
            } else corn = lastBus;
        }

        return minutesToHour(corn);
    }

    private static String minutesToHour(int time) {
        StringBuilder sb = new StringBuilder();

        int hour = time / 60;
        int minutes = time % 60;

        if (hour <= 9) sb.append("0").append(hour);
        else sb.append(hour);

        sb.append(":");

        if (minutes <= 9) sb.append("0").append(minutes);
        else sb.append(minutes);

        return sb.toString();
    }

    private static int hourToMinutes(String time) {
        String[] sp = time.split(":");
        return (Integer.parseInt(sp[0]) * 60 + Integer.parseInt(sp[1]));
    }
}