Programmers : 셔틀버스

문제링크

풀이요약

그리디

풀이상세

1. 콘의 시간에 대하여 가장 중요하게 봐야할 점은 2가지이다.

2. 버스가 도착하기 전 줄을 선 사람들을 모두 태울 여유가 되는 경우 → 콘은 가장 마지막 회차에 오는 버스 시간에 맞춰 오면 된다.

3. 버스가 미리 도착한 사람들을 모두 태울 수 없는 경우 → 콘은 태울 수 인원 마지막 인원보다 1분 빨리와야 한다.

4. timetable의 정보를 숫자화하여 우선순위 큐에 넣는다. 버스가 도착하는 시간과 우선순위 큐에서 가장 앞에 있는 값을 비교했을 때 버스가 도착하는 시간보다 작다면 해당 직원을 태울 수 있다. 이 때, 콘의 시간을 직원이 도착한 시간 -1 의 값으로 업데이트한다. 이 과정을 반복하면 어떤 경우에서든 콘은 반드시 인원 중 가장 마지막에 버스에 타게 된다.

5. 모든 인원을 다 태울 수 있는 경우에는 버스 도착 시간에 맞춰 오는 것이 가장 늦은 시간이므로, 마지막 시간 까지 왔을 때, 인원을 확인하여 남은 경우, 콘의 시간을 버스 마지막 도착시간으로 업데이트 한다.

import java.util.*;
class Solution {
    static PriorityQueue<Integer> pq;
    private static void input(String[] timetable) {
        pq = new PriorityQueue<>();
        for(int i=0; i<timetable.length; i++) {
            String[] curr = timetable[i].split(":");
            int ret = Integer.parseInt(curr[0])*60 +Integer.parseInt(curr[1]);
            pq.add(ret);
        }   
    }
    
    private static int solve(int n, int t, int m) {
        int startTime = 540;
        int cTime = 0;
        int cnt = 0;
        for(int i=0; i<n; i++) {
            startTime = 540 + t * i;
            cnt = 0;
            while(!pq.isEmpty()) {
                int curr= pq.peek();
                if(curr <= startTime && cnt < m) {
                    pq.poll();
                    cnt++;
                    cTime = curr-1;
                } else break;
            }
        }
        if(cnt < m) cTime = startTime;
        return cTime;
    }
    
    private static String output(int ans) {
        String ans_t = String.valueOf(ans/60);
        String ans_m = String.valueOf(ans%60);
        ans_t = ans_t.length() < 2 ? "0" + ans_t : ans_t; 
        ans_m = ans_m.length() < 2 ? "0" + ans_m : ans_m;
        return (ans_t + ":" + ans_m);
    }
    
    public String solution(int n, int t, int m, String[] timetable) {
        input(timetable);
        int ret = solve(n,t,m);
        return output(ret); 
    }    
}