문제

Programmers Lv3, 1차 셔틀버스

핵심

• 입력의 크기가 작아 $O(N^2)$ 이하 알고리즘을 사용한다.

• 크루가 몇 시에 셔틀버스를 기다리는지를 알고 있을 때, 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시간을 구해야 한다.

• 콘은 마지막 버스를 타고 가면 된다. 여기서 문제는 버스 정원이 주어지기 때문에 마지막 버스에 타는 마지막 사람보다 1분이라도 더 빨리 타야한다.

• 버스에 크루를 차례로 태워가면서 마지막 버스 정원에 여유가 있는지에 따라 분기처리하여 여유가 없다면 마지막에 타는 사람보다 1분 더 빨리 타도록 처리하였다. 여유가 있다면 마지막 버스 도착시간에 타면 된다.

개선

• 처음에는 C++에서 split을 구현하여 ":"으로 나누고 hour과 minutes로 나누어 계산하려고 했다. 대소 관계 로직이나 정각에 1분 내림처리 등이 까다로워졌다. 시간 문자열을 어떻게 파싱하는지에 따라 좀 더 간단하게 구현할 수 있다.
• 시간 문자열을 분으로 파싱해서 가지고 있으면, 정각일 때 1분 내림 계산이나 대소 관계 비교를 수월하게 할 수 있었다.

코드

C++

#include <string>
#include <sstream>
#include <algorithm>
#include <queue>

using namespace std;

int convert_minutes(string& arrive_time) {
    int hours, minutes;
    char colon;
    istringstream iss(arrive_time);
    iss >> hours >> colon >> minutes;
    
    return hours * 60 + minutes;
}

string convert_string(int mins) {
    int hours = mins / 60;
    int minutes = mins % 60;
    ostringstream oss;
    oss << (hours < 10 ? "0" : "") << hours << ":" << (minutes < 10 ? "0" : "") << minutes;
    
    return oss.str();
}

string solution(int n, int t, int m, vector<string> timetable) {
    
    string answer = "";
    queue<int> bus;
    queue<int> crew;
    
    sort(timetable.begin(), timetable.end());
    
    for (auto e : timetable) {
        crew.push(convert_minutes(e));
    }
    
    for (int i = 0; i < n; ++i) {
        bus.push(9 * 60 + t * i);
    }

    while (bus.size() > 1) {
        int bus_arrive = bus.front();
        bus.pop();
        for (int i = 0; i < m; ++i) {
            if (!crew.empty() && crew.front() <= bus_arrive) {
                crew.pop();
            }
        }
    }

    if (crew.size() >= m) {
        int crew_last_time = 0;
        for (int i = 0; i < m; ++i) {
            crew_last_time = crew.front();
            crew.pop();
        }
        answer = convert_string(min(crew_last_time - 1, bus.front()));
    } else {
        answer = convert_string(bus.front());
    }
    
    return answer;
}

Java

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


class Solution {

    public int convertMinutes(String arriveTime) {
        LocalTime time = LocalTime.parse(arriveTime, DateTimeFormatter.ofPattern("HH:mm"));
        
        return time.getHour() * 60 + time.getMinute();
    }

    public String convertString(int mins) {
        
        int hours = mins / 60;
        int minutes = mins % 60;
        
        return String.format("%02d:%02d", hours, minutes);
    }
    
    public String solution(int n, int t, int m, String[] timetable) {
        List<String> timetableList = new ArrayList<>(Arrays.asList(timetable));

        String answer = "";
        Queue<Integer> bus = new LinkedList<>();
        Queue<Integer> crew = new LinkedList<>();

        Collections.sort(timetableList);
        
        for (var e : timetableList) {
            crew.add(convertMinutes(e));
        }
        
        for (int i = 0; i < n; ++i) {
            bus.add(9 * 60 + t * i);
        }
        
        while (bus.size() > 1) {
            int busArrive = bus.poll();
            for (int j = 0; j < m; ++j) {
                if (!crew.isEmpty() && crew.peek() <= busArrive) {
                    crew.poll();
                }
            }
        }
        
        if (crew.size() >= m) {
            int crewLastTime = 0;
            for (int i = 0; i < m; ++i) {
                crewLastTime = crew.poll();
            }
            answer = convertString(Math.min(crewLastTime - 1, bus.peek()));
        } else {
            answer = convertString(bus.peek());
        }

        return answer;
    }
}