[프로그래머스]셔틀버스 - JAVA

[프로그래머스]셔틀버스

코딩테스트 연습 - [1차] 셔틀버스

풀이

🪑 문제 자체는 어렵지 않았으나 '시간'이라는 개념이 포함되서 시간 처리를 하는 방법이 익숙하지 않아 매우 어렵게 느껴졌던 문제였다! 시간 처리에서 막혀서 해설을 참고하였다.

 

📝 문제를 정리해 보자!

• 셔틀버스는 오전 9시부터 n회 t분 간격으로 역에 도착하며 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 9시에 도착한 셔틀은 자리가 있다면 9시에 줄을 선 크루도 탈 수 있다.
• 입력 받는 시간의 범위는 00:00 ~ 23:59로 이전날 줄을 선다거나, 줄을 서다 다음날로 넘어가는 일은 없다.
• 크루들의 대기열 도착 시간을 알고 있을 때, 콘이 셔틀버스를 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구한다. 이때 콘과 같은 시간에 도착한 크루가 있다면 같은 시각에 도착한 크루 대기열에서 가장 뒤에 선다.

 

 

🔧 문제를 풀어보자!

1. 크루들의 도착 시간을 "분"으로 변환해 우선순위큐에 담아준다.
2. 현재 시간과 마지막 시간, 현재 시간 셔틀버스에 탄 인원수를 저장하는 변수를 사용한다.
3. 우선순위큐에서 크루의 도착 정보를 하나씩 확인하며 계산한다.
4. 마지막 셔틀 버스에 탄 인원이 m보다 작다면, 해당 셔틀 버스에 콘이 탈 수 있다는 의미이다. 
5. 얻은 마지막 시간 정보를 다시 "시간:분"의 형태로 변환해 준다.

 

 

🔹 크루들의 도착 시간을 "분"으로 변환해 우선순위큐에 담아준다.

• 시간 계산을 할 때에는 같은 단위로 변경해 주는 것이 계산하기 편하다. 
• 여기서는 분 단위로 계산해 주기위해 크루들의 도착 시간 정보에서 '시간'에 해당하는 부분에는 60을 곱하여 더하도록 하였다.
• 우선순위큐를 사용하여 먼저 도착한 크루먼저 처리하도록 할 것이다.

 

 

🔹 현재 시간과 마지막 시간, 현재 시간 셔틀버스에 탄 인원수를 저장하는 변수를 사용한다.

• 현재 시간은 처음 시작시간인 오전 9시로 정하고, 셔틀 버스가 지나갈 때마다 t시간 만큼 더해주면 된다. 
• 마지막 시간은 모든 셔틀버스의 확인이 끝난 후에 결국 구하고자 하는 결과 시간이 될 것이다.
• 셔틀버스에 탄 인원수를 확인하여 콘이 마지막 셔틀버스에 탈 수 있는지 체크할 수 있다.

 

 

🔹 우선순위큐에서 크루의 도착 정보를 하나씩 확인하며 계산한다. 

• 우선순위큐에는 크루들의 도착 시간 정보가 오름차순 정렬되어 있다.
• 우선순위큐에서 가장 빨리 도착한 크루부터 확인한다. 이때 버스 시간보다 이전에 도착한 크루는 버스에 태워주고(큐에서 꺼내고, 셔틀버스에 탄 인원수를 늘려준다.) 아니라면 다음 버스로 넘어간다.
• 현재 셔틀 버스에 크루가 탈 때마다 마지막 시간을 재계산 해준다. 해당 크루 보다 1분 먼저 도착하는 것이 가장 마지막으로 도착하여 해당 버스에 탈 수 있는 시간이므로 현재 크루의 시간 -1을 마지막 시간으로 재설정 한다.

 

 

🔹 마지막 셔틀 버스에 탄 인원이 m보다 작다면, 해당 셔틀 버스에 콘이 탈 수 있다는 의미이다.  

• 콘이 마지막 버스에 타게 되고, 탑승 인원이 꽉 채워지지 않은 경우라면 콘은 버스 도착시간에 동시에 와도 된다.
• 앞서 9시에 도착한 셔틀은 자리가 있다면 9시에 도착한 크루를 태울 수 있다는 조건 때문이다.

 

 

🔹 얻은 마지막 시간 정보를 다시 "시간:분"의 형태로 변환해 준다.

• String.format을 활용하여 hour와 minute정보로 변환해 주었다.

 

 

코드

import java.util.*;
 
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(String table : timetable) {
            int time = Integer.parseInt(table.substring(0, 2)) * 60 + Integer.parseInt(table.substring(3));
            pq.add(time);
        }
     
        int start_time = 9 * 60;
        int last_time = 0;
        int total = 0;
        for(int i = 0; i < n; i++) {
            total = 0;    
            while(!pq.isEmpty()) {
                int current_time = pq.peek();
                if(current_time <= start_time && total < m) {
                    pq.poll();
                    total++;
                } else break;
                last_time = current_time - 1;
            }
            start_time += t;
        }
        if(total < m) last_time = start_time - t;
        
        String hour = String.format("%02d", last_time / 60);
        String minute = String.format("%02d", last_time % 60);
        return hour + ":" + minute;
    }
}