[1차] 셔틀버스

https://school.programmers.co.kr/learn/courses/30/lessons/17678?language=python3 

프로그래머스

문제 요약:

배차간격이 일정 시간 간격으로 최대 몇명씩 태우러 올때 제일 늦게 탈수 있는 시간을 선택하라

 

소요시간:

35분

난이도3

 

코딩:

def make_2(i):
    if len(str(i))==2:
        return str(i)
    else:
        return '0' + str(i)
        
def chage_2_time(i):
    return ''.join([make_2(i//60)]+[':']+[make_2(i%60)])

def solution(n, t, m, timetable):
    for i,time in enumerate(timetable):
        timetable[i] = int(time[0:2])*60 + int(time[3:])
    timetable.sort(reverse = True)
    bustime = [540+t*i for i in range(n)]
    bus = [[] for _ in range(n)]

    #bus에 태울 수 있을만큼 태워라
    for i,time in enumerate(bustime):
        for crew in timetable[::-1]:
            if crew <= time and len(bus[i]) <m:
                bus[i].append(timetable.pop())
            else:
                break
                
    #마지막 버스에 자리가 남았다면
    if len(bus[-1]) <m:
        #그 마지막 버스가 떠나는 시간
        return chage_2_time(bustime[-1])
    #마지막 버스에 가득 차있다면
    else:
        return chage_2_time(bus[-1][-1]-1)

이문제는 그리디문제로 그때그때에 최선의 선택을 해주면 되는데,  마지막 문단만 보면 문제에서 떠나는 시간에 온 크루도 태운다 했으므로 만약 마지막 버스에 자리가 남았다면, 그 버스 시간에 도착하는것이 가장 늦은 시간일 것이며 만약 꽉차 있다면 버스에 탄 인원중 가장 마지막에 온 인원 보다 1 분 빠르게 도착하면 탈 수 있을것이므로 다음과같이 코딩했습니다.  그 위 두번째 문단은 bus라는 이중 배열을 만든뒤 i번째 버스에 탈 수 있는 인원들을 최대한 많이 bus[i]에 넣은 것 입니다. 사실 마지막 버스에 탄 인원 혹은 마지막버스에 마지막으로 탄 인원의 시간만 궁금하기 때문에 마지막만 기록 하면 됩니다.