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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

이 문제를 풀기 위해서는 우선 문자열을 모두 숫자로 바꿔서 시간을 표현해야한다. 하지만 시간과 분을 따로 나눠서 처리하면 비교하기가 어렵기 때문에 1시간은 60분으로 변환하여 모든 시간을 분으로 처리하였다. 그리고 프렌즈를 빨리 도착한 순서대로 정렬한다. 콘이 가장 늦게 버스를 탈 수 있는 시간을 구하는 문제이므로 결국 콘이 마지막 버스를 마지막 순서로 탈 수 있는지를 확인하면 된다. 따라서 프렌즈를 모두 순서대로 버스에 태우고, 마지막 버스가 가득 찬 경우는 마지막에 탄 프렌즈보다 1분 일찍와서 타면 되고, 마지막 버스가 콘이 타지 않았음에도 여유가 있다면 버스 도착 시간에 콘이 오면 된다.

코드

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int time_to_int(string& t) {
    int h = stoi(t.substr(0, 2));
    int m = stoi(t.substr(3, 2));
    return h * 60 + m;
}

string time_to_string(int h, int m) {
    string hour = to_string(h);
    string minute = to_string(m);
    if (hour.length() == 1) hour = '0' + hour;
    if (minute.length() == 1) minute = '0' + minute;
    return hour + ":" + minute;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> table;

    // 모든 시간을 분으로 변경
    for (string t : timetable) 
        table.push_back(time_to_int(t));

    // 도착 순서가 빠른 순서대로 정렬
    sort(table.begin(), table.end());

    int bus = 9 * 60; // 버스 출발 시간
    int ans = 0;
    int idx = 0; // 버스 탑승할 프렌즈의 인덱스
    for (int i = 0; i < n; i++) {
        int count = 0; // 버스에 탑승한 인원
        for (int j = idx; j < table.size(); j++) {
            // 버스에 정원이 남아있을 때
            if (table[j] <= bus) {
                count++;
                idx++;
            }
            // 버스의 정원이 다 찬 경우
            if (count == m) break;
        }
        // 마지막 버스일 때
        if (i == n - 1) {
            // 버스에 정원이 다 차지 않은 경우, 버스 도착하는 시간에 콘이 도착하면 된다
            if (count < m) ans = bus;
            // 버스의 정원이 다 찬 경우, 콘은 마지막에 탄 프렌즈보다 1분 먼저오면 탈 수 있다.
            else ans = table[idx - 1] - 1;
            break;
        }
        bus += t; // 다음 버스가 오는 시간
    }
    answer = time_to_string(ans / 60, ans % 60);
    return answer;
}

Java

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int timeToInt(String time) {
        int h = Integer.parseInt(time.substring(0, 2));
        int m = Integer.parseInt(time.substring(3, 5));
        return h * 60 + m;
    }

    public String timeToString(int h, int m) {
        String hour = String.valueOf(h);
        String minute = String.valueOf(m);
        if (hour.length() == 1) hour = "0" + hour;
        if (minute.length() == 1) minute = "0" + minute;
        return hour + ":" + minute;
    }

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

        ArrayList<Integer> table = new ArrayList<>();
        // 모든 시간을 분으로 변경
        for (String time : timetable)
            table.add(timeToInt(time));

        // 도착 순서가 빠른 순서대로 정렬
        Collections.sort(table);

        int bus = 9 * 60; // 버스 출발 시간
        int idx = 0; // 버스 탑승할 프렌즈의 인덱스
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int count = 0; // 버스에 탑승한 인원
            for (int j = idx; j < table.size(); j++) {
                // 버스에 정원이 남아있을 때
                if (table.get(j) <= bus) {
                    count++;
                    idx++;
                }
                // 버스의 정원이 다 찬 경우
                if (count == m) break;
            }
            if (i == n - 1) {
                // 버스에 정원이 다 차지 않은 경우, 버스 도착하는 시간에 콘이 도착하면 된다
                if (count < m) ans = bus;
                    // 버스의 정원이 다 찬 경우, 콘은 마지막에 탄 프렌즈보다 1분 먼저오면 탈 수 있다.
                else ans = table.get(idx - 1) - 1;
                break;
            }
            bus += t; // 다음 버스가 오는 시간
        }
        answer = timeToString(ans / 60, ans % 60);
        return answer;
    }
}