[프로그래머스 Level 3] 셔틀버스 (Java)

🚀링크

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

💻문제

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

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

셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 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 사이이다.

출력 형식
콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

🌏문제 풀이

이분 탐색을 사용하여 이 문제를 해결할 수 있었습니다.

우선, timetable 배열을 오름차순 정렬하고, "HH:MM" 형태로 주어진 시간을 정수(분) 단위로 바꿔줍니다. 그 다음, 콘이 셔틀버스를 타기 위해 도착하는 시간에 대하여 이분탐색을 시작합니다. 콘은 최대한 늦게 도착하고자 하기 때문에 마지막 셔틀버스에 최소 1자리 이상이 비어있으면 콘이 탑승할 수 있습니다.

이분 탐색이 종료되면, 이를 통해 얻을 값을 문제에서 주어진 출력 형식으로 변환하여 리턴하면 이 문제를 해결할 수 있습니다.

💻코드

import java.util.*;

class Solution {
    
    static int N, T, M;
    
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        
        N = n;
        T = t;
        M = m;
        
        // 마지막 셔틀버스 출발 시간
        int last_time = 540 + ((n - 1) * t);
        
        Arrays.sort(timetable);
        
        int time = binarySearch(timetable, last_time);
        answer = convertToTimeFormat(time);
        
        return answer;
    }
    
    // 문제에서 요구하는 출력 형식으로 변환해주는 메서드
    static String convertToTimeFormat(int time) {
        String hh = String.valueOf(time / 60);
        String mm = String.valueOf(time % 60);
        
        if(hh.length() < 2) {
            hh = "0" + hh;
        }
        if(mm.length() < 2) {
            mm = "0" + mm;
        }
        
        return hh + ":" + mm;
    }
    
    // 콘이 셔틀을 타기 위해 도착한 시간에 대해 이분 탐색
    static int binarySearch(String[] timetable, int x) {
        int L = 0, R = x;
        while(L <= R) {
            int mid = (L + R) / 2;
            
            // 셔틀버스에 탈 수 있는 경우
            if(isAvailable(timetable, mid)) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        
        return R;
    }
    
    // 콘이 셔틀버스에 탈 수 있는지를 리턴해주는 메서드
    static boolean isAvailable(String[] timetable, int k) { 
        
        // 버스 탑승객 수를 카운트할 배열
        int[] passengers = new int[N];
        
        for(int i = 0; i < timetable.length; i++) {
            String[] str = timetable[i].split(":");
            int hh = Integer.parseInt(str[0]);
            int mm = Integer.parseInt(str[1]);
            
            // 크루 도착 시간
            int time = (hh * 60) + mm;
            
            // 콘보다 늦게 줄 선 크루는 고려할 필요가 없음
            if(time > k) {
                break;
            }
            
            for(int j = 0; j < N; j++) {
                // 버스 도착 시간
                int bus_time = 540 + (j * T);
                if(bus_time >= time && passengers[j] < M) {
                    passengers[j]++;
                    break;
                }
            }
        }
        
        return passengers[N - 1] < M;
    }
}