[1차] 셔틀버스 - Java

문제 내용

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

조건

1. 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
2. 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다.
3. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
4. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
5. 단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다.
6. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

0 ＜ n ≦ 10
0 ＜ t ≦ 60
0 ＜ m ≦ 45

• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.

• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

풀이

1. 시간 변환 함수

정답이 HH:MM 포맷이라는 점, 들어오는 HH:MM 포맷의 문자열을 정수형으로 변환해서 처리해주면 더 편할 것 같아 작성했다.

HH:MM 포맷의 시간을 정수형으로 변환해주는 함수, 역으로 변환해주는 함수이다.

    static public int TimeToInt(String time){
        String[] times = time.split(":");
        int hour = Integer.parseInt(times[0]);
        int min = Integer.parseInt(times[1]);
        return hour*60+min;
    }
    
    static public String TimeToStr(int time){
        String hour = String.format("%02d",time/60);
        String min =  String.format("%02d",time%60);
        return hour+":"+min;
    }

2. Crew 들의 정렬

먼저 기다리고 있는 Crew들이 버스에 먼저 탑승해야 한다.

따라서 Crew들을 도착 순서대로 정렬하고 먼저 도착한 Crew가 버스에 우선적으로 탑승해야하므로 이를 처리하기 쉬운 자료 구조로 변환해줄 필요를 느꼇다.

따라서 Crew 들의 도착 정보가 있는 timeTable을 우선순위 큐로 변환해 주었다.

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        
        String answer = "";
 
        PriorityQueue<Integer> waiters = new PriorityQueue<Integer>();
        setPriorityQueue(timetable,waiters);
        
        return answer;
    }


    static public void setPriorityQueue(String[] timetable,PriorityQueue<Integer> waiters){
        for(String time:timetable){
            waiters.add(TimeToInt(time));
        }
    }

3. 콘의 도착 시점 계산

1,2 번 과정을 통해 문제를 편하게 풀 환경을 만들었다.

이제, 문제의 핵심인 콘의 도착 시점을 계산해야한다.

콘은 가능한 늦게 버스정류장에 도착해야한다.

즉, 막차를 타줘야한다.

막차에 콘이 탈 자리가 있다면 콘은 막차가 오는 시간에 도착하면 된다.
하지만, 막차에 자리가 없다면 막차에 마지막에 타는 사람보다 1분 빨리 오면 된다

1분 빨리오는 이유는 마지막 사람과 같은 시간에 도착할 경우 마지막 사람보다 더 뒤에 서기 때문에 막차에 탑승하지 못하기 떄문이다.

코드 구현

따라서 막차가 올 때 까지 (arrivedBusCount <= n-1),

Crew 들을 계속 버스에 태우면서 위 조건을 검사한다.

만약 막차이면서 마지막 사람이 탈 차례가 되었다면 (boardCount == m-1 && arrivedBusCount ==n-1)

콘은 마지막 사람보다 1분 빨리 도착하도록 한다

만약 막차가 왔지만 해당 막차에 탈 자리가 있는 경우 해당 조건문에 걸리지 않아

    if(boardCount == m-1 && arrivedBusCount ==n-1) {// 막찬데 자리가 없을 경우 
          return answer= TimeToStr(waiters.poll()-1);
     }

while 문을 빠져 나가게 된다.

따라서 이때는 막차 시간을 반환해주면 된다.

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        
        String answer = "";
        int arrivedBusCount = 0;
        int arrivedBusTime = TimeToInt("09:00");
        PriorityQueue<Integer> waiters = new PriorityQueue<Integer>();
        setPriorityQueue(timetable,waiters);
        
        while(arrivedBusCount<=n-1){
            if(arrivedBusCount!=0)arrivedBusTime +=  t;
            int boardCount = 0;
            while(waiters.size()!=0 && boardCount <=m-1){
                if(waiters.peek()>arrivedBusTime)break;
                if(boardCount == m-1 && arrivedBusCount ==n-1) {// 막찬데 자리가 없을 경우 
                    return answer= TimeToStr(waiters.poll()-1);
                }
                waiters.poll();
                boardCount++;
            }
            arrivedBusCount++;
        }
        
        //막차에 탈 수 있는 경우 
            
        return TimeToStr(arrivedBusTime);
    }

전체 코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        
        String answer = "";
        int arrivedBusCount = 0;
        int arrivedBusTime = TimeToInt("09:00");
        PriorityQueue<Integer> waiters = new PriorityQueue<Integer>();
        setPriorityQueue(timetable,waiters);
        
        while(arrivedBusCount<=n-1){
            if(arrivedBusCount!=0)arrivedBusTime +=  t;
            int boardCount = 0;
            while(waiters.size()!=0 && boardCount <=m-1){
                if(waiters.peek()>arrivedBusTime)break;
                if(boardCount == m-1 && arrivedBusCount ==n-1) {// 막찬데 자리가 없을 경우 
                    return answer= TimeToStr(waiters.poll()-1);
                }
                waiters.poll();
                boardCount++;
            }
            arrivedBusCount++;
        }
        
        //막차에 탈 수 있는 경우 
            
        return TimeToStr(arrivedBusTime);
    }
    
    static public int TimeToInt(String time){
        String[] times = time.split(":");
        int hour = Integer.parseInt(times[0]);
        int min = Integer.parseInt(times[1]);
        return hour*60+min;
    }
    
    static public String TimeToStr(int time){
        String hour = String.format("%02d",time/60);
        String min =  String.format("%02d",time%60);
        return hour+":"+min;
    }
    
    static public void setPriorityQueue(String[] timetable,PriorityQueue<Integer> waiters){
        for(String time:timetable){
            waiters.add(TimeToInt(time));
        }
    }
}