[Programmers] Level 3 : 셔틀버스

문제 링크

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

프로그래머스

💡 풀이

콘이 정류장에 도착 가능한 제일 늦은 시각을 구하는 문제이기 때문에, 셔틀의 막차 시간을 이용해 풀이할 수 있습니다. 

다음과 같은 과정으로 풀이할 수 있습니다. 

1. 우선 모든 시간을 분 단위로 계산합니다. 
2. 계산된 `timetable`을 오름차순으로 정렬합니다. → 여기서 저는 우선순위 큐를 사용했습니다.
3. 첫 셔틀부터 막차 전 버스까지 셔틀의 도착 시간으로 반복문을 진행합니다. 
   1. 이때, 셔틀의 도착시간보다 일찍 도착한 크루가 있다면, m명까지 태워 보냅니다. →  `poll`을 통해 꺼내기
4. 막차의 도착 시간 기준으로 콘의 도착 시간을 계산합니다.
   1. m번째 대기자가 없는 경우 or m번째 대기자가 막차 도착시간보다 늦게 도착하는 경우 → `콘의 도착 시간 == 막차 도착 시간`
   2. 그 외의 경우 → m번째 대기자보다 1분 빠르게 도착. 즉, 콘의 도착 시간 = m번째 대기자 도착 시간 - 1

오름차순 정렬 때문에 우선순위 큐를 사용했지만, 초기에 정렬이 한 번만 필요하기 때문에 일반적인 `ArrayList`를 사용해도 좋을 것 같습니다.

전체 코드

전체적인 코드는 다음과 같습니다. 

import java.util.*;

class Solution {
    PriorityQueue<Integer> timeQ = new PriorityQueue<>();
    
    public String solution(int n, int t, int m, String[] timetable) {        
        for(String time : timetable) {
            timeQ.offer(convertTimeToInt(time));
        }
        
        int start = 9*60 - t;
        for(int i = 0; i < n - 1; i++) {
            // 셔틀의 도착 시간
            start += t;
            for(int j = 0; j < m; j++) {
                if(!timeQ.isEmpty() && timeQ.peek() <= start) {
                    timeQ.poll();
                } else {
                   break; 
                }
            }
        }
        
        // 마지막 셔틀 = 타야할 셔틀
        start += t;
        int resultTime = 0;
        // m번째 대기자가 없는 경우 : 셔틀 도착시간이 콘의 도착시간
        if(timeQ.size() < m) {
            resultTime = start;
        } 
        // m번째 대기자가 존재하는 경우
        else {
            // m번째 대기자 시간 확인
            for(int i = 0; i < m - 1; i++) {
                timeQ.poll();
            }
            int mth = timeQ.poll();

            // m번째 대기자가 도착 시간보다 늦은 경우
            if(mth > start) {
                resultTime = start;
            } else {
                resultTime = mth - 1;
            }
        }
        
        return convertTimeToString(resultTime);
    }
    
    private int convertTimeToInt(String timeStr) {        
        int hour = Integer.parseInt(timeStr.substring(0, 2));
        int min = Integer.parseInt(timeStr.substring(3, 5));

        return hour * 60 + min;
    }
    
    private String convertTimeToString(int time) {
        int hour = time / 60;
        int min = time % 60;
        
        String hourStr = hour < 10 ? "0" + hour : hour + "";
        String minStr = min < 10 ? "0" + min : min + "";
        
        return hourStr + ":" + minStr;
    }
}