알고리즘102 :: KAKAO_셔틀버스

몇번 읽고 문제가 잘 이해가 안되었습니다. ㅠ__ㅠ

그래서 몇 가지 검색해보다가 알게된 사실을 예제로 설명해 보겠습니다. 

example1)

n=1, t=1, m=5, timetable=["08:00","08:01","08:02","08:03"] 

셔틀은 09:00 부터 출발합니다. 셔틀은 1번 1분 간격으로 역에 도착하지만 한번에 5명을 태울 수 있으므로 08:00~08:03, (콘이 탈 시각 08:04) 모두 태울 수 있습니다. 따라서, 

example2)

n=2, t=10, m=2, timetable=["09:10","09:09","08:00"]

마찬가지로 셔틀이 09:00 부터 출발하는것을 생각해보면 08:00 에 한명을 태웁니다. 셔틀이 총 2번 10분 간격으로 오기때문에 다음 올 셔틀은 09:10 입니다. 이때, 대기하고 있던 인원들의 각각의 시간은 09:09, 09:10 (정렬했을때) 이다. 만약, 이럴경우 콘은 탈 수 없게 됩니다. 왜냐하면 셔틀은 한번에 2명을 태울 수 있기 때문입니다. 따라서, 콘이 사무실에 도착하되 제일 늦은 시간은 09:10 도착한 사람보다 1분 일찍 빠른 09:09 가 되어야 합니다. 

마지막 예제 example5) 를 보면

n=10, t=60, m=45, timetable=[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]

셔틀은 09:00부터 출발합니다. 최대 10번에 60분 간격으로 역에 도착하기 때문에 600분(=10시간) 이후에 마지막 셔틀이 오게 됩니다. 10시간 후에는 18:00가 됩니다. 

for(int i=0; i<timetable.length; i++){
            int hour = Integer.parseInt(timetable[i].substring(0,2)); //시간
            int min = Integer.parseInt(timetable[i].substring(3,5)); //분
            currentTime[i] = hour*60+min; //currentTime에 저장
        }
 Arrays.sort(currentTime); //빠른 순서대로 온 인원들을 우선적으로 앞으로 배정(대기시간)

int[] bus = new int[n];
        for(int i=0; i<n; i++){
            bus[i] = 540+t*i; //셔틀은 09:00 부터 출발하므로 분으로 환산하면 540, 배차 간격에 따라
                              +됩니다.
       	}

int[] waitOfPeople = new int[n]; //버스당 탈 수 있는 인원 
        int[][] waitOfPeopleTime = new int[n][m]; //버스당 탄 인원의 도착 시간 
        for(int i=0; i<currentTime.length; i++){
            for(int j=0; j<n; j++){
                if(currentTime[i]<=bus[j]){ //bus에 탑승하기 위해서는 현재 도착한 시간이 더 빨라야 합니다.
                    if(waitOfPeople[j]>=m){ //인원이 초과.
                        continue; //다음 버스에 인원을 태움
                    }
                    waitOfPeopleTime[j][waitOfPeople[j]] = currentTime[i];
                    //j번째 버스에 waitOfPeople[j] 인원의 currentTime[i] bus에 탑승하기 위해 도착한 시간
                    ++waitOfPeople[j];
                    //버스에 탑승할 수 있으므로 한명 증가
                    break;
                }
            }
        }

if(waitOfPeople[n-1]>=m){//마지막 버스에 탄 인원수가 넘친다면 마지막 인원이 탑승한 시간보다 1분더 일찍 오면 됩니다.
            int hour = waitOfPeopleTime[n-1][m-1]/60; //마지막 버스에 마지막 인원의 버스를 기다리는 시간
            int min = waitOfPeopleTime[n-1][m-1]%60; //마지막 버스에 마지막 인원의 버스를 기다리는 분
            if(min-1<0){
                answer = (hour-1>9 ? hour-1 : "0"+(hour-1))+":59";
                //9보다 크면 10 이므로 앞에 0이오는 구조가 될 수 없음
                //09:00 면 08:59 출력을 맞춰줘야 하기 때문에 59
            }else{
                answer = (hour>9 ? hour : "0"+hour)+":"+(min-1>9?min-1:"0"+(min-1)); 
                //위와 마찬가지로 min-1>9보다 크면 그대로, 그렇지 않으면 앞에 0을 붙여줘야 함
            }
        }else{ //마지막 버스에 제일 마지막을 탑승하면 됀다. 
            answer = (bus[n-1]/60>9?bus[n-1]/60:"0"+bus[n-1]/60)+":"+(bus[n-1]%60>9?bus[n-1]%60:"0"+bus[n-1]%60);
            //마지막 셔틀에 탑승하면 되기때문에 bus[n-1] : 마지막 버스에 탑승한 인원의 시간이 됩니다.
        }

 

종합

import java.util.*;
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        int[] currentTime = new int[timetable.length];
        for(int i=0; i<timetable.length; i++){
            int hour = Integer.parseInt(timetable[i].substring(0,2));
            int min = Integer.parseInt(timetable[i].substring(3,5));
            currentTime[i] = hour*60+min;
        }
        Arrays.sort(currentTime);
        int[] bus = new int[n];
        for(int i=0; i<n; i++){
            bus[i] = 540+t*i;
        }
        int[] waitOfPeople = new int[n]; //버스당 탈 수 있는 인원 
        int[][] waitOfPeopleTime = new int[n][m]; //버스당 탄 인원의 도착 시간 
        for(int i=0; i<currentTime.length; i++){
            for(int j=0; j<n; j++){
                if(currentTime[i]<=bus[j]){
                    if(waitOfPeople[j]>=m){ //인원이 초과되었다.
                        continue; //다음 버스에 인원을 태우자
                    }
                    waitOfPeopleTime[j][waitOfPeople[j]] = currentTime[i];
                    ++waitOfPeople[j];
                    break;
                }
            }
        }
        if(waitOfPeople[n-1]>=m){//마지막 버스에 탄 인원수가 넘친다면 마지막 인원이 탑승한 시간보다 1분더 일찍 오면 됀다.
            int hour = waitOfPeopleTime[n-1][m-1]/60; //마지막 버스에 마지막 인원의 버스를 기다리는 시간
            int min = waitOfPeopleTime[n-1][m-1]%60; //마지막 버스에 마지막 인원의 버스를 기다리는 분
            if(min-1<0){
                answer = (hour-1>9 ? hour-1 : "0"+(hour-1))+":59";
            }else{
                answer = (hour>9 ? hour : "0"+hour)+":"+(min-1>9?min-1:"0"+(min-1)); 
            }
        }else{ //마지막 버스에 제일 마지막을 탑승하면 됀다. 
            answer = (bus[n-1]/60>9?bus[n-1]/60:"0"+bus[n-1]/60)+":"+(bus[n-1]%60>9?bus[n-1]%60:"0"+bus[n-1]%60);
        }
        return answer;
    }
}

*reference: https://4ngs.tistory.com/27 

감사합니다.