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

문제 설명

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

문제 풀이

• 직관적으로 이분 탐색을 이용하여 풀이하였다.
• 콘의 도착시간을 기준으로 이분 탐색을 시행하고 탈 수 있는 시간의 최대값을 구한다.
• 이분 탐색에 앞서 각 시간별 도착 인원 count[1440]배열과 누적합 배열 preSum[1440]을 연산해 준다 (특정 시간 구간의 탑승 인원을 O(1)로 구하기 위함.)
• 이분 탐색에 의해 콘의 도착시간이 정해지면 모든 셔틀 시간을 반복하여 콘의 도착시간 이후 셔틀 시간에서 탑승이 가능하면 도착시간을 늘리고 탑승이 불가능하면 도착시간을 줄여준다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        //초기화
        int[] count = new int[1440];
        for (int i = 0; i < timetable.length; i++) {
            String line = timetable[i];
            StringTokenizer st = new StringTokenizer(line, ":");
            int hour = Integer.parseInt(st.nextToken());
            int min = Integer.parseInt(st.nextToken());
            count[hour * 60 + min]++;
        }

        int[] preSum = new int[1440];
        int sum = 0;
        for (int i = 0; i < 1440; i++) {
            sum += count[i];
            preSum[i] = sum;
        }

        //이분탐색 수행 (시간 범위에 따라서)
        int lo = 0;
        int hi = 540 + (n-1) * t + 2; //막차 시간 + 2
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            //해당 시간에 콘이 탔을때 탈 수 있는지 출력
            boolean result = false;

            int remain = preSum[mid];
            int move = preSum[540];
            for (int i = 0; i < n; i++) {
                int time = 540 + t * i;
                //현재 시간 이후면 -> 콘 이전 승객 중 현재 시간 이전까지 탑승한 승객 수 줄임
                if (time < mid) {
                    if (i != 0) 
                        move += (preSum[time] - preSum[time - t]);
                    int diff = move - m < 0 ? move : m;
                    remain -= diff;
                    move -= diff;
                }
                //현재 시간 이하이면
                else {
                    remain -= m;
                    //탑승 가능한 경우 (콘 이전승객들이 모두 탑승)
                    if (remain < 0) {
                        result = true;
                        break;
                    }
                }
            }

            //가능하면 lo = mid;
            if (result) lo = mid;
                //불가능하면 hi = mid;
            else hi = mid;
        }
        //lo를 시간으로 변환
        return (lo / 60 < 10 ? "0" : "") + lo / 60 + ":" + (lo % 60 < 10 ? "0" : "") + lo % 60;
    }
}