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

문제 링크

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

풀이 과정

Arrays.sort(timetable, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        String[] o1_splited = o1.split(":");
        String[] o2_splited = o2.split(":");

        if (o1_splited[0].equals(o2_splited[0]))
            return o1_splited[1].compareTo(o2_splited[1]);
        return o1_splited[0].compareTo(o2_splited[0]);
    }
});

먼저 파라미터로 받는 timetable 문자열 배열을 시간의 오름차순으로 정렬합니다.

Map<Integer, String> map = new HashMap<>();
String now = "09:00";

for (int i = 0; i < n; i++) {
    map.put(i, now);

    DateTimeFormatter dtf = DateTimeFormatter.ofPattern("HH:mm");
    LocalTime next = LocalTime.parse(now, dtf).plusMinutes(t);

    now = next.toString();
}

셔틀은 09:00 를 기점으로, t 분 간격으로 총 n 회 운행됩니다. LocalTime 클래스를 이용하여, 다음 번 운행 시간을 구하고, map 에 인덱스 와 운행 시간 을 기록합니다. 이는 이후의 코드에서 리스트를 사용하고, 같은 인덱스를 참조해 셔틀의 운행 시간을 얻어내기 위함입니다.

DateTimeFormatter dtf = DateTimeFormatter.ofPattern("HH:mm");
int idx_schedule = 0;
int idx_timetable = 0;

while (idx_schedule < schedule.length && idx_timetable < timetable.length) {
    LocalTime lt_schedule = LocalTime.parse(map.get(idx_schedule), dtf);
    LocalTime lt_timetable = LocalTime.parse(timetable[idx_timetable], dtf);

    if (schedule[idx_schedule].size() + 1 <= m && (lt_timetable.isBefore(lt_schedule) || lt_timetable.equals(lt_schedule))) {
        schedule[idx_schedule].add(timetable[idx_timetable]);
        idx_timetable++;
    } else
        idx_schedule++;
}

리스트를 돌며, 셔틀의 각 운행 시간에 탑승할 수 있는 크루들의 도착 시간을 기록합니다. 리스트를 위한 인덱스 idx_schedule 과, 문제에서 주어진 timetable 을 위한 인덱스 idx_timetable 을 0으로 초기화한 후, 순회합니다.

if (schedule[idx_schedule].size() + 1 <= m && (lt_timetable.isBefore(lt_schedule) || lt_timetable.equals(lt_schedule))) {
    schedule[idx_schedule].add(timetable[idx_timetable]);
    idx_timetable++;
} else
    idx_schedule++;

while 내부 코드는 다음 로직과 같습니다. 해당 크루가 탑승할 수 있는 공간이 남아 있고, 크루의 도착 시간( lt_timetable )이 셔틀의 운행 시간( lt_schedule ) 과 같거나 더 이른 경우, 해당 셔틀에 크루의 대기열 도착 시간을 기록합니다. 그렇지 않다면 탑승을 못하는 것을 의미하므로, 해당 크루부터는 다음 셔틀로 넘겨서 위 조건을 다시 확인합니다.

int last = schedule.length - 1;

if (schedule[last].size() + 1 <= m) {
    answer = map.get(last);
} else {
    for (int j = 0; j < schedule[last].size(); j++) {
        LocalTime tmp = LocalTime.parse(schedule[last].get(j), dtf).minusMinutes(1);

        if (j + 1 <= m) {
            answer = tmp.toString();
        }
    }
}

콘은 가장 늦은 시간에 셔틀 대기열에 도착하려고 합니다. 따라서, 제일 마지막에 운행하는 셔틀을 기준으로 콘의 도착 시간을 지정할 수 있습니다. 따라서, last 인덱스에 해당하는 셔틀만 확인하면 됩니다.

if (schedule[last].size() + 1 <= m) {
    answer = map.get(last);
}

마지막으로 운행하는 셔틀의 자리가 비어 있다면, 콘은 해당 셔틀에 탑승할 수 있으므로, 셔틀 운행 시간에 딱 맞춰 도착해도 됩니다.

else {
    for (int j = 0; j < schedule[last].size(); j++) {
        LocalTime tmp = LocalTime.parse(schedule[last].get(j), dtf).minusMinutes(1);

        if (j + 1 <= m) {
            answer = tmp.toString();
        }
    }
}

그렇지 않다면, 해당 셔틀을 탑승하는 크루들의 도착 시간보다 1분 먼저 도착했을 때 탈 수 있나를 확인하면서, 콘의 도착 시간을 늘려 나갑니다.

코드

import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.util.*;

public class Main {
    public static String solution(int n, int t, int m, String[] timetable) {
        String answer = "";

        Arrays.sort(timetable, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String[] o1_splited = o1.split(":");
                String[] o2_splited = o2.split(":");

                if (o1_splited[0].equals(o2_splited[0]))
                    return o1_splited[1].compareTo(o2_splited[1]);
                return o1_splited[0].compareTo(o2_splited[0]);
            }
        });

        Map<Integer, String> map = new LinkedHashMap<>();
        String now = "09:00";
        
        for (int i = 0; i < n; i++) {
            map.put(i, now);

            DateTimeFormatter dtf = DateTimeFormatter.ofPattern("HH:mm");
            LocalTime next = LocalTime.parse(now, dtf).plusMinutes(t);

            now = next.toString();
        }

        List<String>[] schedule = new ArrayList[map.size()];
        for (int i = 0; i < schedule.length; i++)
            schedule[i] = new ArrayList<>();

        DateTimeFormatter dtf = DateTimeFormatter.ofPattern("HH:mm");
        int idx_schedule = 0;
        int idx_timetable = 0;

        while (idx_schedule < schedule.length && idx_timetable < timetable.length) {
            LocalTime lt_schedule = LocalTime.parse(map.get(idx_schedule), dtf);
            LocalTime lt_timetable = LocalTime.parse(timetable[idx_timetable], dtf);

            if (schedule[idx_schedule].size() + 1 <= m && (lt_timetable.isBefore(lt_schedule) || lt_timetable.equals(lt_schedule))) {
                schedule[idx_schedule].add(timetable[idx_timetable]);
                idx_timetable++;
            } else
                idx_schedule++;
        }

        int last = schedule.length - 1;

        if (schedule[last].size() + 1 <= m) {
            answer = map.get(last);
        } else {
            for (int j = 0; j < schedule[last].size(); j++) {
                LocalTime tmp = LocalTime.parse(schedule[last].get(j), dtf).minusMinutes(1);

                if (j + 1 <= m) {
                    answer = tmp.toString();
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        solution(1, 1, 5, new String[]{"08:00", "08:01", "08:02", "08:03"});
//        solution(2, 10, 2, new String[]{"09:10", "09:09", "08:00"});
//        solution(2, 1, 2, new String[]{"09:00", "09:00", "09:00", "09:00"});
//        solution(1, 1, 5, new String[]{"00:01", "00:01", "00:01", "00:01", "00:01"});
//        solution(1, 1, 1, new String[]{"23:59"});
//        solution(10, 60, 45, new String[]{"23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"});
    }
}