[2018 Kakao Blind Recruitment 1차] Q4. 셔틀버스(C++, Python, JAVA)

programmers.co.kr/learn/courses/30/lessons/17678

 

알고리즘 분류

Greedy, Simulation

 

풀이

어렵게 생각하면 한도 끝도 없이 어렵지만 잘 생각해보면 콘을 제외한 크루들을 규칙대로 다 태운 후 제일 마지막 버스에 자리가 남아있다면 콘은 마지막 버스가 출발하는 시간에 도착하면 됩니다. 자리가 남아있지 않다면 제일 마지막 버스에서 제일 마지막 사람보다 1분만 빨리 도착하면 됩니다.

 

미리 크루를 도착 시간에 대해 정렬해두고 각 버스에 대해서 남아있는 크루 중 가장 빨리 도착한 사람을 태울 수 있는지 확인합니다. 이를 반복해서 각 버스에 크루를 최대한 많이 태워서 끝까지 시뮬레이션 하면 됩니다. 

 

시간은 모두 분으로 환산한 후 계산을 진행했습니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

int time2min(string t){
    int h = (t[0] - '0') * 10 + t[1] - '0';
    int m = (t[3] - '0') * 10 + t[4] - '0';
    return 60*h + m;
}

string min2time(int t){
    string h = to_string(t / 60);
    if(h.size() == 1) h = '0'+h;
    string m = to_string(t % 60);
    if(m.size() == 1) m = '0'+m;
    return h + ":" + m;
}

string solution(int n, int t, int m, vector<string> timetable) {
    vector<int> tlist;
    for(auto s : timetable)
        tlist.push_back(time2min(s));
    sort(tlist.begin(), tlist.end());
    // 셔틀이 출발하는 시간(departure time, 초기 값은 09:00에 대응되는 540)
    int dept = 540; 
    // 현재 보고 있는 tlist의 index
    int idx = 0;
    // 현재 셔틀에 타고 있는 사람의 수
    int cnt = 0;
    for(int i = 0; i < n; i++){
        cnt = 0;
        // 현재 보는 크루가 출발 시간 이전에 도착했고 버스 승객 수가 m명 미만일 경우
        while(idx < tlist.size() && tlist[idx] <= dept && cnt < m){
            cnt++;
            idx++;
        }
        dept += t;
    }
    if(cnt != m) return min2time(dept - t);
    else return min2time(tlist[idx-1] - 1);
}

 

time2min, min2time은 각각 HH:MM 형식의 시간과 분 단위 시간을 서로 변환해주는 함수입니다.

 

풀이에서 설명한 것과 같이 n번에 걸쳐 for문을 돌면서 승객을 계속 태웁니다. for문 안에서 탑승을 처리할 때 삐끗하면 인덱스를 1 차이로 벗어나서 한 명을 더 태우거나, 덜 태우거나, 런타임에러가 나오기 쉬워서 조심해야 합니다.

 

마지막에 cnt != m이면 버스에 빈자리가 있으니 마지막 버스의 출발 시간을 반환하고 cnt == m이면 버스에 빈자리가 없으니 마지막 승객보다 1분 빨리 도착합니다.

 

코드(Python)

def time2min(t):
    return int(t[:2])*60 + int(t[3:])

def min2time(t):
    return str(t//60).zfill(2)+ ":" + str(t%60).zfill(2)

def solution(n, t, m, timetable):
    tlist = [time2min(x) for x in timetable]
    tlist.sort()
    '''
    dept : 셔틀이 출발하는 시간(depature time, 초기 값은 09:00에 대응되는 540)
    idx : 현재 보고 있는 tlist의 index
    cnt : 현재 셔틀에 타고 있는 사람의 수    
    '''
    dept, idx, cnt = 540, 0, 0
    for i in range(n):
        cnt = 0
        while idx < len(tlist) and tlist[idx] <= dept and cnt < m:
            cnt += 1
            idx += 1
        dept += t
    if cnt != m: return min2time(dept - t)
    else: return min2time(tlist[idx-1] - 1)

time2min, min2time은 각각 HH:MM 형식의 시간과 분 단위 시간을 서로 변환해주는 함수입니다. zfill과 int 함수 등을 이용해 한 줄로 구현할 수 있습니다. tlist는 list comprehension을 통해 효과적으로 선언할 수 있습니다.

 

풀이에서 설명한 것과 같이 n번에 걸쳐 for문을 돌면서 승객을 계속 태웁니다. for문 안에서 탑승을 처리할 때 삐끗하면 인덱스를 1 차이로 벗어나서 한 명을 더 태우거나, 덜 태우거나, 런타임에러가 나오기 쉬워서 조심해야 합니다.

 

마지막에 cnt != m이면 버스에 빈자리가 있으니 마지막 버스의 출발 시간을 반환하고 cnt == m이면 버스에 빈자리가 없으니 마지막 승객보다 1분 빨리 도착합니다.

 

코드(JAVA)

import java.util.*;

class Solution {
    int time2min(String t){
        int h = (int)(t.charAt(0) - '0') * 10 + (int)(t.charAt(1) - '0');
        int m = (int)(t.charAt(3) - '0') * 10 + (int)(t.charAt(4) - '0');
        return 60*h + m;
    }
    
    String min2time(int t){
        String h = Integer.toString(t/60);
        if(h.length() == 1) h = "0" + h;
        String m = Integer.toString(t%60);
        if(m.length() == 1) m = "0" + m;
        return h + ":" + m;     
    }
    
    public String solution(int n, int t, int m, String[] timetable) {
        int len = timetable.length;
        int[] tlist = new int[len];
        for(int i = 0; i < len; i++)
            tlist[i] = time2min(timetable[i]);
        Arrays.sort(tlist);
        // 셔틀이 출발하는 시간(departure time, 초기 값은 09:00에 대응되는 540)
        int dept = 540; 
        // 현재 보고 있는 tlist의 index
        int idx = 0;
        // 현재 셔틀에 타고 있는 사람의 수
        int cnt = 0;
        for(int i = 0; i < n; i++){
            cnt = 0;
            // 현재 보는 크루가 출발 시간 이전에 도착했고 버스 승객 수가 m명 미만일 경우
            while(idx < len && tlist[idx] <= dept && cnt < m){
                cnt++;
                idx++;
            }
            dept += t;
        }
        if(cnt != m) return min2time(dept - t);
        else return min2time(tlist[idx-1] - 1);
    }
}

time2min, min2time은 각각 HH:MM 형식의 시간과 분 단위 시간을 서로 변환해주는 함수입니다.

 

풀이에서 설명한 것과 같이 n번에 걸쳐 for문을 돌면서 승객을 계속 태웁니다. for문 안에서 탑승을 처리할 때 삐끗하면 인덱스를 1 차이로 벗어나서 한 명을 더 태우거나, 덜 태우거나, 런타임에러가 나오기 쉬워서 조심해야 합니다.

 

마지막에 cnt != m이면 버스에 빈자리가 있으니 마지막 버스의 출발 시간을 반환하고 cnt == m이면 버스에 빈자리가 없으니 마지막 승객보다 1분 빨리 도착합니다.