프로그래머스 연습 - [1차] 셔틀버스 (2018 카카오 블라인드 채용), 자바, 우선순위 큐, 문자열)

<문제를 이해하기 위해 오신분을 위한 문제 정리>

1. 9 : 00부터 무조건 버스가 출발합니다.

2. t분 간격으로 m명까지 태우는, 하루에 n번 운행하는 버스가 있습니다.

3. 주인공 콘은 운행 가능한 버스 맨 마지막에 타려고 합니다.

4. 그러므로 timetable에 나와 있는 시간에 못탈 것 같으면 해당 인원들보다 빨리 도착해야 할 수 있습니다.

5. 이러할 때 콘이 가장 마지막 시간에 출발하는 버스의 시간을 구하세요. 

# 주소

https://school.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 사이의 값이 될 수 있다.

입출력 예제

ntmtimetableanswer

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"

해설 보러가기

# 문제 해설 및 코드 리뷰

import java.util.PriorityQueue;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        int time = 0;
        int start = 540;

        PriorityQueue<Integer> crews = new PriorityQueue<>();
        for (String times : timetable)
            crews.offer(toTimes(times));

        int count = 0;
        while(n--> 0) {
            count = 0;
            while (!crews.isEmpty()) {
                int crew = crews.poll();
                if (crew <= start && count < m) {
                    time = crew - 1;
                    count++;
                }else {
                    crews.offer(crew);
                    break;
                }
            }
            start += t;
        }

        if (count < m) {
            time = start - t;
        }
        return toString(time);
    }

    static int toTimes(String s) {
        String[] split = s.split(":");
        int hour = Integer.parseInt(split[0]);
        int minute = Integer.parseInt(split[1]);
        return hour * 60 + minute;
    }

    static String toString(int val) {
        String hStr = String.format("%02d", val / 60);
        String mStr = String.format("%02d", val % 60);
        return hStr +":"+mStr;
    }
}

아~ 이 문제 저는 못풀었습니다.

아뇨 정확히는 문제 이해하는데 2시간 걸리고 구현하는데 2시간 걸리고 하다가 문자열 처리에 너무 애먹어서 풀이를 봤습니다.

근데 풀이를 보니 제가 기존에 풀던 코드랑 다 똑같은데 toString함수를 활용하는 부분엔서 달랐습니다.

무슨 말이냐면 저는 처음에 구현할 때 예외의 경우가 너무 많을 것 같아서 9시 이전에 도착하는 것들은 따로 리턴하는걸 분기를 계속 시켜줬거든요...

분명 그게 아닐거 같다는 직감은 왔는데 그게 아니면 어떻게 짤지 모르겠더라고요.

정답 코드는 간결할거라 생각했는데 제 코드는 너무 길어져서... 어쨌든 보면 다 그말이 그말이긴 한데 너무 어렵게 생각한 것 같더라구요..

또한 저는 timetable배열을 가져와서 시간과 분을 따로 변수로 나누어서 관리했었습니다.

때문에 Comparator라는 인터페이스를 implements할 수 밖에 없었고 오름차순으로 나타내기 위해 compare메서드를 활용했었습니다만 굳이 시간을 시간 + 분으로 관리할 필요가 없더라고요.

진작 이랬음 좋았을텐데요.

제가 깨달은 것을 정리하자면

1. 시간을 굳이 시간 + 분으로 관리하지말고 분단위로 관리하고 나중에 60으로 나누어서 시간을 표현한다.

2. 문제가 이해가 안될 땐 검색을 해보자... (이해가 안되어서 2시간이나 날렸습니다. 아무리 읽어도 왜 시간이 더 감소하는지 도저히 이해가 안되더라구요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ)

 

코드를 보며 최대한 이해를 돕도록 해보겠습니다.

int time = 0;
int start = 540;

PriorityQueue<Integer> crews = new PriorityQueue<>();
for (String times : timetable)
    crews.offer(toTimes(times));

정답이 되는 time코드와 버스 출발 시간을 나타내는 start를 각각 int타입으로 선언합니다.

그리고 start는 540으로 저장한 것은, 9 : 00에 출발하는 start를 분으로 나타낸 것입니다.

저는 우선순위 큐를 사용했는데 최초에 전 ArrayList를 사용하여 정렬했습니다. 여러분들은 어떤걸 쓰셔도 됩니다.

ArrayList를 쓰실 분은 데이터를 담고 오름차순으로 정렬한 뒤 이후에 대기열에 있는 인원을 담을 때 탐색가능한 곳 까지 탐색한다고 가정할 때 변수 하나에 담고 저장하며 관리하셔야 합니다. (최초에 저도 그렇게 했습니다.)

큐가 훨씬더 데이터를 넣고 빼기 편하기 때문에 큐를 이용하여 풀이하겠습니다.

 

이후부터 for문을 이용하여 queue에 시간을 넣을텐데요.

toTimes 함수는 다음과 같습니다.

static int toTimes(String s) {
    String[] split = s.split(":");
    int hour = Integer.parseInt(split[0]);
    int minute = Integer.parseInt(split[1]);
    return hour * 60 + minute;
}

substring으로 구현하셔도 무방합니다!

이후가 정말 중요합니다.

int count = 0;
while(n--> 0) {
    count = 0;
    while (!crews.isEmpty()) {
        int crew = crews.poll();
        if (crew <= start && count < m) {
            time = crew - 1;
            count++;
        }else {
            crews.offer(crew);
            break;
        }
    }
    start += t;
}

 

총 n번 탐색을 위해 while문을 돌아주겠습니다.

이 때 start는 버스 출발 시간이라고 제가 말씀드렸습니다.

start보다 crew의 시간이 적고 count < m이면 (버스에 더 탈 여유가 있다면) time은 crew - 1로 잡습니다.

무슨 의미인지 봅시다.

crew가 start보다 작다는 것은 버스가 출발하기 전을 의미합니다.

대기열에 사람이 줄서서 기다리고 있다는 것입니다. 이 상황일 때, 버스가 오기전 총 인원을 세어보려고 합니다.

줄 서 있는 인원중 m명까지는 버스에 타고 그다음부터는 다음 버스를 기다리는 것입니다.

따라서 m명이 딱 맞춰졌을 때 그 이후 poll()해서 뽑은 인원은 다시 queue에 넣고 break하여 다음 버스를 기다리는 것입니다.

버스 start시간도 t만큼 더해주어야 하구요.

그렇다면 정답이 될 time은 왜 crew에서 1을 뺀 값일까요?

time = crew - 1;

자 우리는 콘이 게으르다고 했었죠???

예제로 설명을 간단히 드려보겠습니다.

[08:00], [09:09], [09:10] 이렇게 입력을 받는다고 한다면 우리는 09시에 버스는 출발하기 때문에 08시에 온 승객을 먼저 태우고 떠나보냅니다. (버스2대, 10분간격으로 총 2명 제한)

이후 09:10에 버스가 오게 될텐데 저 2번째와 3번째 승객을 태우면 콘이 못타죠???

때문에 콘은 09:10의 친구 대신에 본인이 타야만 합니다. (마지막 친구는 택시라도 타야죠..)

따라서 if문에서 count가 m보다 굳이 작다고 둔 것도 마지막 m명까지는 태워보겠다는 것을 의미하고 그 친구보다는 1분 빠르게 오는 것이 콘이기 때문에 09 : 10에서 1을 뺀 09 : 09가 time에 담기게 되는 것입니다.

이후는 당연히 n이 0이 되어 while문에서 빠져나오게 되며 start는 t를 더해지겠지요.

if (count < m) {
    time = start - t;
}
return toString(time);

이후, 버스가 만석일 때와 아닐 때를 한 번 더 구분지어주셔야 합니다.

만약 이랬는데도 버스가 만석이라면 맨 마지막에 타려다가 못탄 사람의 시간에서 1을 뺀 시간이니 그대로 return해주시면 되고 만약 그럼에도 버스에 자리가 여유가 있다면 아까 더해준 t를 start에서 빼주시면 되겠습니다.

왜냐하면 버스의 출발 시간에 콘이 타야 탈 수 있기 때문이지요.

감사합니다.