Implementation-[1차]셔틀버스

문제

(링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17678 )

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

핵심 아이디어

구현+우선순위 큐

사람의 사고(아이디어)를 코드에 나타내기 까다로운 구현문제이다.

핵심 아이디어는 콘은 무조건 막차를 탄다는 것이다.

만약 막차 대기 인원이 최대 탑승인원(m)보다 적으면 그냥 막차 도착 시간에,

많으면 마지막 탑승 직원보다 1분 일찍 온다.

따라서 우선순위 큐를 사용해 타임 테이블의 전체 인원을 대기열에 세우고 빠른 순으로 버스에 태우고,

막차까지 태우고 남은 인원을 체크한다.

제약사항이 많아 예외처리를 많이 해줘야할 것 같지만 (23:59 분에 선 사람들은 다음날 버스를 탈 수 없다, 대기 인원이 최대 탑승인원보다 많을 수 있다 등) 위의 핵심 아이디어 (타임테이블 정렬+막차 탑승)만 충족하면 자동으로 충족된다.

Point

‘문자 → 시간, 시간 → 문자’ 암기

• 더하고 빼는 등 시간 값 자체를 변경하는 로직이 사용된다면 숫자형으로 다뤄주는게 좋다. 최종적인 답만 문자열로 변환하여 반환한다

• 시간 값 자체를 변경하지 않고 그냥 그루핑만 필요했다면 문자열을 그대로 사용한다

• 더하고 빼는 단위에 따라 어떤 숫자로 표현할 지 결정한다

  ex) 더하고 빼는게 ‘분 단위’ —> int minutes, ‘초 단위‘ —> long seconds

• 문자 → 시간 : Integer.parseInt(table.substring(0,2))*60 + Integer.parseInt(table.substring(3))

• 시간 → 문자 : String.format(“%02d:%02d”, lastTime/60, lastTime%60)

코드

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 startTime = 9*60 ;
        int lastTime = 0 ; 
        int count = 0; 
        for(int i = 0 ; i < n ; i++){
            count = 0 ; 
            while(!pq.isEmpty()){
                int boardTime = pq.peek() ; 
                if(boardTime <= startTime && count < m){
                    pq.poll() ;
                    count++ ; 
                }else{
                    break ; 
                }
                lastTime = boardTime-1 ; // last member' boarding time -1
            }
            startTime += t; 
        }
        if(count < m) 
            lastTime = startTime-t ; // in the end of loop, added t to last bus time
        
        return String.format("%02d:%02d", lastTime/60, lastTime%60) ;
    }
}