[2018 KAKAO] 셔틀버스

[2018 KAKAO] 셔틀버스

제출일 : 2020-08-29

문제 풀이 시간 : 2H 30M

---

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

문제 설명

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

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

• 셔틀은 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

문제 풀이 접근

문제를 풀며 꽤나 시간이 많이 걸렸습니다.

처음에 작성한 코드는 주어진 테스트 케이스는 맞지만 체점결과 1개의 케이스가 실패하여 처음부터 코드를 작성하였습니다.

도착시간을 우선순위 큐에 담고 버스가 도착하는 시간에 탑승하는 인원을 확인하고 현재 도착한 셔틀버스를 타기 위한 가장 늦은 시간을 구하는 방식으로 문제를 접근하여 풀었습니다. 22번 테스트케이스가 어떠한 것인지 자꾸 실패하였고 예외를 계속 코딩하다보니 코드가 너무 지저분해지기만 해 코드를 버리고 새로 작성하였습니다.

저는 우선순위큐를 사용했지만 다른 사람들의 풀이를 보니 대부분 String배열을 정렬하여 문제를 해결한것을 보고 나는 왜 이렇게 간단하게 생각하지 못했나 하는 생각을 했습니다.

아래의 코드는 모든 시간에 셔틀버스를 탄 사람들을 각각 다 저장하고 뒤에서부터 탐색하여 빈자리가 있다면 셔틀버스가 오는 시간이 가장 늦은 시간이 되고 빈자리가 없다면 앞사람보다 1분 빨리 도착하는 경우를 구했습니다.

코드

언어 : JAVA

package Programmers.kakao;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class kakao2018_4_셔틀버스 {
    public static void main(String[] args) {
        System.out.println(solution(1, 1, 5, new String[] { "08:00", "08:01", "08:02", "08:03" }));
        System.out.println(solution(2, 10, 2, new String[] { "09:10", "09:09", "08:00" }));
        System.out.println(solution(2, 1, 2, new String[] { "09:00", "09:00", "09:00", "09:00" }));
        System.out.println(solution(1, 1, 5, new String[] { "00:01", "00:01", "00:01", "00:01", "00:01" }));
        System.out.println(solution(1, 1, 1, new String[] { "23:59" }));
        System.out.println(solution(10, 60, 5, new String[] { "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" }));
    }

    public static String solution(int n, int t, int m, String[] timetable) {

        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });
        for (int i = 0; i < timetable.length; i++) {
            StringTokenizer st = new StringTokenizer(timetable[i], ":");
            pq.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
        }

        int H = 9, M = 0;
        int[][][] bus = new int[n][m][2];
        int[][] time = new int[n][2];
        for (int k = 0; k < n; k++) {
            time[k][0] = H;
            time[k][1] = M;
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                bus[k][i][0] = -1;
            }
            while (cnt < m && !pq.isEmpty()) {
                int[] now = pq.peek();
                if (now[0] < H || (now[0] == H && now[1] <= M)) {
                    bus[k][cnt] = pq.poll();
                    cnt++;
                } else
                    break;
            }
            // 시간 증가
            H = (M + t >= 60) ? H + 1 : H;
            M = (M + t >= 60) ? M + t - 60 : M + t;
        }

        for (int k = n - 1; k >= 0; k--) {
            for (int i = m - 1; i >= 0; i--) {
                if (bus[k][i][0] == -1)
                    return String.format("%02d:%02d", time[k][0], time[k][1]);

                if (i > 0 && bus[k][i - 1][0] == bus[k][i][0] && bus[k][i - 1][1] == bus[k][i][1])
                    continue;

                if (bus[k][i][1] - 1 < 0)
                    return String.format("%02d:%02d", bus[k][i][0] - 1, 59);
                else
                    return String.format("%02d:%02d", bus[k][i][0], bus[k][i][1] - 1);

            }
        }
        return "";
    }
}