[자바/우선순위 큐] 프로그래머스 셔틀버스

1. 문제

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

프로그래머스

 

2. 풀이

• 문제 이해부터 잘해야 된다.
• 즉, 콘이 버스를 타는 경우를 두가지로 나누자면
  1. 마지막 버스가 만원이면, 마지막으로 도착한 사람보다 더 빨리 도착해서 마지막 버스를 탄다
     • 이 경우, 마지막으로 도착한 사람보다 1분만 먼저 도착하면 탈 수 있다
  2. 버스가 널널하면, 가장 마지막에 도착하는 버스를 탄다.
     • 마지막으로 출발하는 버스 시간에 오면 바로 탈 수 있으므로 마지막으로 출발하는 버스 시간에 맞춰서 온다.
• 시간 구분을 편하게 하기 위해 시간을 모두 분 단위로 바꿔준다. 그리고 그 값을 우선순위큐에 넣어줘서 자동으로 도착한 시간대로 오름차순으로 정렬되게 한다.
• 우선순위큐에서 한 명씩 빼가면서, (1)의 케이스를 구하기 위해 탄 사람들의 도착 시간을 체크한다.
• 모든 사람이 버스에 타면(우선순위큐가 NULL이 되면) 마지막 버스에 탄 사람의 수를 확인하여 (1)과 (2)의 케이스로 나눠 타야할 시간을 구한다.

 

3. 코드

import java.util.*;

class Solution {
    
    public String solution(int n, int t, int m, String[] timetable) {
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 도착한 시간을 분으로 변환, 오름차순으로 정렬
        for(int i = 0; i < timetable.length; i++){
            String[] ss = timetable[i].split(":");
            pq.add(Integer.parseInt(ss[0]) * 60 + Integer.parseInt(ss[1]));
        }

        int shuttleTime = 9 * 60; // 버스 출발 시간
        int lastShuttleTime = shuttleTime + (n-1) * t; // 마지막 버스 출발 시간
        int lastRideTime = shuttleTime; // 마지막으로 승객이 탄 시간
        int cnt = 0; // 현재 버스에 탄 사람
        
        while(!pq.isEmpty() && shuttleTime <= lastShuttleTime){
            cnt = 0; 
            // 버스에 정원이 차지 않고, 남은 사람 중 가장 먼저온 사람이 셔틀 시간보다 먼저 오면
            while(cnt < m && !pq.isEmpty() && pq.peek() <= shuttleTime){
                lastRideTime = pq.poll(); // 마지막으로 버스 탄 사람이 도착한 시간 갱신
                cnt++; // 현재 버스 탄 사람 증가
            }
            shuttleTime += t; // 다음 버스 오는 시간 갱신
        }
        
        int ansTime = 0;
        if(cnt == m) { // 마지막 버스가 만원인 경우
            ansTime = lastRideTime - 1; // 마지막 도착한 시간보다 1분 먼저 옴
        }else{  // 마지막 버스가 만원이 아닌 경우(사람보다 버스가 넉넉할 수도 있으므로)
            ansTime = lastShuttleTime; // 마지막 버스 출발 시간
        }
        
        return String.format("%02d:%02d", ansTime / 60, ansTime % 60);
    }
}