[pro] 프로그래머스 level3 17678 셔틀버스 (Java) - 우선순위 큐

[문제]

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

프로그래머스

 

[풀이]

계산하기 편하도록 도착시각을 모두 분으로 변환하여 우선순위 큐에 넣는다.

n번의 셔틀 운행에 대하여 크루가 셔틀 출발 시각 이전에 도착 및 버스 탑승 인원이 남아 탑승가능하다면 탑승시킨다.

이때 탑승한 크루가 마지막 탑승 크루일 수 있으므로  정답을 크루탑승시각-1 로 갱신해준다.

만약 마지막 버스에 자리가 남아있다면 그 버스의 출발시각이 가능한 가장 늦은 도착 시각이 된다. 

 

[코드]

 

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        //콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(String time:timetable){
            pq.add(convertToTime(time));
        }
        
        int departureTime = 9*60;
        List<List<Integer>> bus = new ArrayList<>();
        for(int i=0; i<n; i++)
            bus.add(new ArrayList<>());
        
        int ans = 0;
        for(int i=0; i<n; i++){
            while(!pq.isEmpty()){
                int crew = pq.poll();
                //버스 출발 시간보다 일찍 왔고, 버스 인원이 아직 다 차지 않았다면
                if(bus.get(i).size() < m && crew<=departureTime){
                    bus.get(i).add(crew); //버스에 탈 수 있음 
                    ans = crew - 1; //마지막 탑승자라면 그 탑승자보다 빨리 와야 사무실로 갈 수 있음
                }
                else{
                    pq.add(crew);
                    break;
                }   
            }
            departureTime += t;
        }
        
        //마지막 버스에 자리가 남으면 그 버스의 출발시각에 도차하면 됨
        if(bus.get(n-1).size() < m){
            ans = departureTime - t;
        }
        
        answer += converToString(ans);
        
        return answer;
    }
    
    static int convertToTime(String s){
        String[] arr = s.split(":");
        int hour = Integer.parseInt(arr[0]);
        int min = Integer.parseInt(arr[1]);
        return hour*60+min;
    }
    
    static String converToString(int time){
        String hour = String.format("%02d", time/60);
        String min = String.format("%02d", time%60);
        return hour+":"+min;
    } 
}