문제

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

특정 규칙에 따라 운행되는 셔틀버스에 탑승하기 위해 언제 나가야 할지 구하자!

---

입력

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

---

출력

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

---

풀이

제한조건

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

접근방법

정렬을 통한 단순 구현문제라고 생각했다.

우선 timetable이 HH:mm형식으로 주어지므로, 해당 데이터를 편하게 관리하기 위한 class를 생성했다.
HH:mm형식이지만, 사실 시간 단위의 비교는 분으로 통일 해서 계산할 수 있다.
따라서 분 단위로 계산된 시간만 생각한다.

또한 대기열에 도착하는 순서대로 탑승하는 것이므로 시간 순 정렬이 필요하다. timetick에 따라 정렬을 할 수 있게 구현을 한다.

그리고 마지막으로 현재 시간을 다시 HH:mm형식으로 변환할 수 있는 기능과, 다음 버스가 도착할 시간을 계산할 수 있게 시간을 흘려보내는 함수를 구현한다.

이제 단순하게 구현하는것만 남았다.

구현과정

1. 각 버스가 도착한다. ( n번 반복 )
2. 버스보다 먼저 도착한 크루가 있다면 m명 까지 탑승한다.
	a.m명이 넘는다면 해당 크루는 다음 버스에 탑승한다.
3. 다음 버스가 올때까지, 즉 t시간을 흘려보낸다.

이후. 마지막 버스가 온다면
- 해당 버스에 m명이 모두 탑승한 경우
	-> 마지막에 탑승한 크루보다 1분 일찍 탑승.
    ( 크루를 도착 시간에 따라 정렬했으므로, 마지막 탑승 크루가 가장 늦은 시간이다 )
- 해당 버스에 m명이 모두 탑승하지 않은 경우
	-> 버스 시간에 맞추어 탑승

class Time implements Comparable<Time>{
    int timetick;
    
    Time(String str){
        String[] splitedLine = str.split(":");
        timetick = Integer.parseInt(splitedLine[0])*60 + Integer.parseInt(splitedLine[1]);
    }
    Time(){};
    Time(int timetick){
        this.timetick = timetick;
    }
    
    public String toFormatting(){
        String hour = Integer.toString(timetick / 60);
        String min = Integer.toString(timetick % 60);
        if(hour.length() == 1)
            hour = "0" + hour;
        if(min.length() == 1)
            min = "0" + min;
        
        return hour + ":" + min;
    }

    public void after(int k){
        timetick += k;
    }
    public int compareTo(Time o){
        return this.timetick - o.timetick;
    }
    
}

---

코드

import java.util.*;

class Time implements Comparable<Time>{
    int timetick;
    
    Time(String str){
        String[] splitedLine = str.split(":");
        timetick = Integer.parseInt(splitedLine[0])*60 + Integer.parseInt(splitedLine[1]);
    }
    Time(){};
    Time(int timetick){
        this.timetick = timetick;
    }
    
    public String toFormatting(){
        String hour = Integer.toString(timetick / 60);
        String min = Integer.toString(timetick % 60);
        if(hour.length() == 1)
            hour = "0" + hour;
        if(min.length() == 1)
            min = "0" + min;
        
        return hour + ":" + min;
    }

    public void after(int k){
        timetick += k;
    }
    public int compareTo(Time o){
        return this.timetick - o.timetick;
    }
    
}
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        List<Time> list = new ArrayList();
        for(String str : timetable)
            list.add(new Time(str));
        
        Collections.sort(list);
        
        Time base = new Time("09:00");
        Time result = new Time();
        int idx = 0;
        for (int i = 1; i <= n ; ++i) {  // 총 n대의 셔틀 버스 운행 
            int count = 0;  // 현재 버스의 탑승자 수
            for (int j = idx; j < list.size(); ++j) {
                if (list.get(j).timetick > base.timetick)
                    break;
                
                // 현재 버스보다 먼저 대기하던 사람
                count++;
                idx++;
                if (count == m) // 최대 인원이 모두 탑승한 경우.
                    break;
                
            }
            if (i == n){  // 마지막 버스일 경우 처리
                if(count == m) // 마지막 탑승자 보다 1분 빨리 와야 한다.
                    result.timetick = list.get(idx-1).timetick - 1;
                else
                    result.timetick = base.timetick;
            }
            base.after(t);
        }
        
        return result.toFormatting();
    }
}