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

문제설명

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

셔틀 버스가 9시부터 시간간격 t로 n회온다. 사람들은 이 셔틀버스를 타기 위해 00시01분부터 23시 59분 사이에 줄을 선다. 이때, 어떻게 줄을 서야 가장 타이트하게 회사로 가는 차를 탈 수 있을지(막차를 타고 갈 수 있을지) 시간을 찾는 문제이다.

시간은 1분 단위이다.

접근

문제 이해에 따른 목표값 찾기

문제를 이해하는데만 20분이 걸렸다. 문제를 정확히 이해했다면 결국엔 언제 줄을 서야 막차를 타고 갈 수 있는지에 대한 문제이므로 마지막 차에 타려고 줄을 섰을 때는 2가지 경우로 나눌 수 있다.

1)마지막 차가 도착했을 때 대기줄 인원이 버스의 정원을 초과했을 경우

• 이땐 가장 마지막에 도착한 사람보다 1분 빨리 도착하면 막차를 탈 수 있다.

2)마지막 차가 도착했을 때 버스 정원보다 대기줄 인원이 적을 경우

• 이땐 차가 도착한 시간에 정확히 오면 가장 늦은 시간이다.(문제에서 09:00에 오면 09:00에 온 사람까지 태우고 간다고 설명되어 있다.)

그렇다면 어떻게 절차를 구성할 것인가?

요점은 마지막 버스의 대기줄 인원 수

마지막 버스의 대기줄에 사람이 얼마나 있을지 알아내는 절차를 짜는 것과 같다. 거꾸로 생각해보겠다. 마지막 차의 사람을 구하려 하면 그 이전에 대기줄이 있었는지 없었는지 알아야 한다. 또 이를 알려면 그전으로... 결국엔 처음부터 마지막까지 사람이 줄을 서고, 태우고가는 과정을 밟아 마지막을 구하면 된다.

버스는 많아봐야 10번 운행하고 정원은 m명, 크루는 최대 2000명이므로 queue를 구현할 경우 10번 지점에 대한 pop 수 2000번이면 (연산 수 2000) 가능하다.

한편으로 프로세스 스케줄링 문제와 유사하다보면 된다. 크루는 서비스를 바라고 있고, 버스는 서비스 공급자.

이런 관점으로 구현하면 매우 간단히 풀릴 것이라 본다.

유의해야할 사항

1. 크루의 도착시간은 00:0123:59이다. 그리고 23시 59분엔 집으로 돌아간다., 콘의 값은 00:0023:59이다.
   • 크루가 00:00에 도착하지 않으므로 1분을 뺀 것으로 00:00시간에 맞출 수 있다.
2. 버스 도착시간에 온 사람도 태운다
   • 위에서 적었 듯 09:00에 도착했으면 09:00에 출발한다.

절차

1.매 버스가 도착할 때마다 버스 도착시간 이전 사람을 que에 push해준다.

• 이 때 미리 자료구조를 우선순위큐로 구현하여 pop하든지, 정렬하여 pop해준다면 매번 n회 탐색할 필요가 없다.

2.버스가 출발할 때 정원 수 만큼 pop해준다.

• 한편으로 1,2과정을 차라리 timetable을 queue로 보고 정렬 또는 우선순위큐로 만들어 했어도 좋았을 것 같다.

3.마지막 버스출발 때 대기인원 수를 구한다.

​ 3-1.이때 대기인원수가 정원을 초과했다면 정원까지 pop한다음 한번 더 pop했을 때 도착시간을 확인한 뒤 그 사람보다 1분 빨리 도착한다.

​ 3-2. 정원을 초과하지 않았다면 출발시간 때 도착한다.

​

구현

from queue import Queue

def ConvertTimeIntToString(h,m):
    #시
    if h < 10:
        h = '0' + str(h)
    else:
        h = str(h)
    # 분
    if m < 10:
        m = '0' + str(m)
    else:
        m = str(m)
    return h + ':' + m

def passTime(curTime,t):
    h = int(curTime[:2])
    m = int(curTime[3:])
    #시간더하기
    if m+t >= 60:
        m = (m+t)-60
        h += 1
    else:
        m += t
    return ConvertTimeIntToString(h,m)

def GetPreTime(time):
    h = int(time[:2])
    m = int(time[3:])

    #숫자로 바꾸기
    if m == 0:
        h -= 1
        m = 59
    else:
        m -= 1
    return ConvertTimeIntToString(h,m)

def solution(n, t, m, timetable):
    answer = ''
    preN = n-1
    timetable.sort()
    tableLen = len(timetable)
    i = 0

    startTime = "09:00"
    que = Queue()
    #막차전까지 모두 태우기
    for _ in range(preN):
        #출발시간 전까지 타임테이블에 있는 사람 세우기
        while i<tableLen and timetable[i]<=startTime:
            que.put(timetable[i])
            i += 1

        #정원수 만큼 대기자 pop!
        tempM = m
        while not que.empty() and tempM != 0:
            que.get()
            tempM -= 1

        startTime = passTime(startTime,t)

    #막차 사람 태우기
    while i<tableLen and timetable[i]<=startTime:
        que.put(timetable[i])
        i += 1

    #정원이 남아있다면 출발때 타기
    if que.qsize()<m:
        answer = startTime
    #정원 초과라면 마지막 대기자 사람보다 1분빨리 오기
    else:
        #마지막 정원자전까지 pop
        tempM = m-1
        while tempM != 0:
            que.get()
            tempM -= 1

        lastPersonTime = que.get()
        answer = GetPreTime(lastPersonTime)

    return answer

이번 구현에선 배울점이 많다.

1. 시간보다는 가독성

   • 마지막버스나 그 이전 버스나 동작은 동일하나 매 반복마다 마지막버스인지 확인하여 마지막버스 때 취할 동작을 작성해주기엔 속도가 늦어질까봐 그리 안 적었는데 어차피 반복횟수가 10번밖에 안되므로 그리 해주는게 더욱 좋았을 것 같다.

   • for i in range(n):
         if i == n-1:
             @!@#!@#

   • 위와 같이 해주자.

2. and연산 순서를 변경하여 가독성을 높히자

   • while timetable[i]<=startTime and i<tableLen:
         que.push(timetable[i])

   • 위는 반복문을 도는 조건을 버스 출발 시간까지 도착한 사람들을, 인덱스초과하지 않는 선에서 que에 넣어달라! 하는 문장이다. 말로 표현하면 군더더기 없으나 위처럼 코드를 작성하면 i==tableLen일 경우에 timetable[i]를 참조하여 인덱스 에러가 발생한다.

   • 그렇다면 아래처럼 순서를 바꾸어 작성해주면 해결된다. and연산은 하나라도 0이면 false이므로 프로그래밍 언어에서 보통 피연산자 값이 0이 뜨는 순간 더 계산하지 않고 False를 반환해주기 때문에 timetable[i]를 참조하는 일은 발생하지 않는다.

   • while i<tableLen and timetable[i]<=startTime:
         que.push(timetable[i])

3. 서로 다른 진법에 대한 연산

   • 내가 작성한 코드를 보면 분이 60분을 넘어갔을 때, 00분에서 1분 빼졌을 때를 구하려고 하드코딩을 하였다. 단위를 하나로 통일함으로써 해결할 수 있다.
   • 시간으로 환산할 경우엔 소수점이 발생하므로 더 낮은 단위인 분으로 환산하는게 좋다.
   • 따라서 분으로 바꾼 후에 처리!

반성

요 며칠동안 어떻게 접근할 지, 신경써야할 조건은 따로 표시해두고, 까다로운 절차는 손으로 미리 작성해보고 접근하니 생각한대로 코딩이 된다. 즉, 생각한대로 구현하지 못하여 발생한 디버깅은 현저히 줄어들었다.

하지만 속도는 아직 느리다. 유튜브에서 코딩대회 문제를 실시간으로 푸는 영상을 보니 충격먹었다. 물론 엄청 잘하니까 자신감에 올린 영상이겠지만 문제를 보고 이해하자마자 엄청 빠른 속도로 다다다다닥 적어가는 것이다.

마치 글로 쓰는 것보다 코드로 작성하는게 더 편하다는 느낌이였다. 나는 글로 작성하고 코드로 옮기지만 그 사람은 코드가 마치 글인 것처럼 작성했다.

이를 보니 어떤 수준까지 가야하는지 감이 왔고 가독성이라는 단어에 대해 위와 같은 범주까지 포함 시키로 마음 먹었다.