[프로그래머스] 카카오 블라인드 리쿠르트 2018 - 셔틀 버스 (Java)

 

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

문제 설명

셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 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 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

n	t	m	timetable	answer
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"

---

풀이

문제 자체는 크게 어렵지 않다고 생각하는데 실제로 시험 때 단순 시간 계산 미스로 헤매다가 멘붕에 올지도 모르겠다.

 

우선, String 형태의 시간들을 계산하기 편하게 분으로 변경(parseTimeToMinute())시켰다.

그리고 본격적으로 로직을 수행하기 전 timeTable이 시간 순으로 정렬되어야 했는데, 그냥 우선순위큐를 사용하여 분으로 환산한 도착시간들을 오름차순으로 꺼낼 수 있도록 하였다.

 

버스 출발 시간을 나타내는 minutes 변수의 초기값은 첫 버스가 운행하는 시간인 09:00를 분으로 환산한 값으로 두었다.

버스는 n번 운행하기 때문에 이를 for문으로 작성하였고, 매 순회 끝마다 minutes에 t분만큼씩 더했다.

 

passengers는 매 운행때 탑승자들의 도착시간을 저장하는 리스트다. 문제의 주인공 콘은 가장 늦게 나올 수 있는 시간을 찾는 것이기 때문에 모든 버스의 탑승 정보를 기억할 필요 없이 마지막 버스에 대한 탑승자 정보만 기억하고 있으면 된다. 그렇기 때문에 매 순회때마다 passengers를 초기화를 시켜준다.

버스 출발 시간인 minute보다 일찍 도착한 탑승자의 도착시간을 큐에서 꺼내서 저장하였다.

단, passengers의 사이즈가 버스의 최대 탑승 인원 수(m) 이하일 때까지만 저장한다.

 

결국 마지막에 passengers에 담겨있는 값들은 마지막 버스에 대한 탑승자 도착 시간들이다.

minutes는 마지막 버스의 도착 시간에 t분이 더 더해진 값이기 때문에 minutes -= t를 해줘야 마지막 버스 도착 시간이 된다.

 

만약, passengers의 사이즈가 m보다 작다면(버스에 여유 자리가 있다면) 버스 출발 시간에 도착하여도 되므로 마지막 버스 출발 시간을 시간 포맷으로 변경하여 리턴하면 된다.

 

만약, passengers의 사이즈가 m이라면(버스에 여유 자리가 없다면) 버스를 타고 있는 누군가보다는 못해도 1분은 일찍 도착해야한다. 콘을 제외하고는 passengers의 마지막 원소 값이 가장 마지막으로 도착한 사람의 시간이므로, 해당 시간(passengers.get(passengers.size()-1)) 보다 1분 빠른 시간을 리턴하면 된다.

 

코드

import java.util.*;

public class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        int minutes = parseTimeToMinutes("09:00");

        Queue<Integer> arrivedTimes = new PriorityQueue<>();

        for (String arrivedTime : timetable) {
            arrivedTimes.add(parseTimeToMinutes(arrivedTime));
        }

        List<Integer> passengers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            passengers = new ArrayList<>();

            while (!arrivedTimes.isEmpty()) {
                if (minutes < arrivedTimes.peek()) {
                    break;
                }

                if (passengers.size() == m) {
                    break;
                }

                passengers.add(arrivedTimes.poll());
            }
            minutes += t;
        }

        minutes -= t;
        if (passengers.size() < m) {
            return formatMinuteToTime(minutes);
        }

        int lastPassenger = passengers.get(passengers.size() - 1);
        return formatMinuteToTime(lastPassenger - 1);

    }

    private int parseTimeToMinutes(String time) {
        int hour = Integer.parseInt(time.split(":")[0]);
        int minute = Integer.parseInt(time.split(":")[1]);

        return hour * 60 + minute;
    }

    private String formatMinuteToTime(int minutes) {
        int hour = minutes / 60;
        int minute = minutes % 60;

        StringBuilder stringBuilder = new StringBuilder();
        if (hour < 10) {
            stringBuilder.append("0");
        }

        stringBuilder.append(hour)
                     .append(":");

        if (minute < 10) {
            stringBuilder.append("0");
        }

        stringBuilder.append(minute);

        return stringBuilder.toString();
    }
}