프로그래머스 셔틀버스

2021-02-16

1. 프로그래머스 셔틀버스

1.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]

1.2. 컴퓨팅적 사고

해당 문제는 시간으로 주어진 값을 파싱하여 푸는 단순 구현문제였습니다. 시간관련한 문제에서 처음에 접근할때 어려움이 조금이 있었는데, 차근차근 하나씩 풀어나간 문제였습니다.

제가 문제를 풀때 고려하였던 점은 다음과 같습니다.

(1) 타임테이블로 주어진 값들을 모두 "분"단위로 변경
(2) 순서대로 온다는 보장이 없으므로 sort
(3) 셔틀버스 시작시간은 09:00 이므로 9 * 60
(4) 셔틀버스 운행전에 도착한 크루가 있는경우(크루의 탑승객의수 증가 + 크루의 진행된 인덱스의 개수)
(5) 버스에 정원이 다 차지 않은 경우, 버스도착시간에 콘 도착
(5) 버스 정원이 모두 가득찼을 경우, 운행을 종료시키고 마지막지점까지 도달하여 콘은 마지막 프렌즈 도착시간 이전타임 보다 1분 일찍 오면 콘이 오는시간
(6) 아직 더 탈인원이 있다면 다음 운행버스 호출
(7) 정답은 hh:mm 형식이므로 convertToString 함수 호출하여 정답 반환

해당 문제에서 가장 중요했던점은 시간을 "분단위"로 변환하는것이고 해당 로직에서 셔틀이 시작하는 시점은 09:00부터 시작된다는점입니다. 처음에 문제를 이해하는데 많은 시간이 소요된 것 같습니다.

1.3. 소스코드

public class programmers_셔틀버스_kgh {
    public static void main(String[] args) {
        solution(1,1,5,new String[]{"08:00","08:01","08:02","08:03"});
    }
    static String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        //1. 모든 타임테이블 시간을 분단위로 변경
        int[] times = convertToTime(timetable);
        //2. 도착순서대로 정렬을 진행
        Arrays.sort(times);

        int busTime = 9 * 60;
        // 몇번째 크루까지 탑승했는지
        int busIdx = 0;
        int cornTime = 0;

        // 운행횟수만큼 진행
        for(int i=0; i<n; i++){
            // 버스탑승인원
            int busCrewCnt = 0;
            for(int j=busIdx; j<times.length; j++){
                // 버스 출발전에 도착한크루가 있는 경우
                if(times[j] <= busTime){
                    busCrewCnt++;
                    busIdx++;
                }
                // 버스 정원 꽉찬 경우
                if(busCrewCnt == m){
                    break;
                }
            }

            if(i == n-1){
                // 버스에 정원이 다 차지 않은 경우, 버스도착시간에 콘 도착
                if(busCrewCnt < m){
                    cornTime = busTime;
                }
                // 버스의 정원이 다 찬경우, 콘은 마지막에 탄 프렌즈보다 1분먼저오면 탈수 있음
                else {
                    cornTime = times[busIdx-1]-1;
                    break;
                }
            }
            // 다음 셔틀 호출하기
            busTime += t;
        }
        answer = convertToString(cornTime / 60, cornTime % 60);
        System.out.println(answer);
        return answer;
    }

    /**
     * 분단위 hh:mm형식 변환
     * @param h
     * @param m
     * @return
     */
    private static String convertToString(int h, int m) {
        String hour = Integer.toString(h);
        String minute = Integer.toString(m);
        if(hour.length() == 1){
            hour = "0" + hour;
        }
        if(minute.length() == 1){
            minute = "0" + minute;
        }
        return hour + ":" + minute;
    }

    /**
     * hh:mm형식 분단위 변환
     * @param timetable
     * @return
     */

    private static int[] convertToTime(String[] timetable) {
        int[] times = new int[timetable.length];
        for(int i=0; i<timetable.length; i++){
            String[] time = timetable[i].split(":");
            int h = Integer.parseInt(time[0]);
            int m = Integer.parseInt(time[1]);
            int total = h * 60 + m;
            times[i] = total;
        }
        return times;
    }
}

AlgorithmProgrammers

1. 프로그래머스 셔틀버스

1.1. 문제

1.2. 컴퓨팅적 사고

1.3. 소스코드