수퍼마켓 계산줄

https://www.codewars.com/kata/57b06f90e298a7b53d000a86

수퍼마켓의 계산 줄을 처리하는데 소요되는 전체 시간을 구하는 프로그램을 작성한다.

요건

문제의 입력으로는 정수 리스트와 정수값 하나가 제시된다. 리스트는 고객을 의미하며, 다른 정수값은 계산대의 개수이다. 리스트 내의 각 정수값은 개별 고객으로 각 고객이 계산을 마치는데 필요한 시간을 정의한다.

규칙

• 빈 계산대가 없으면 나머지 손님은 모두 기다려야 한다.
• 빈 계산대가 나타나면 계산줄을 무조건 앞에서부터 처리된다.
• 모든 손님이 계산대 통과를 완료해야 한다.

곧이 곧대로 구현하기

n 개의 계산대를 마련해놓고 앞에서부터 손님을 빈 계산대로 보낸다. 1초 경과 후 모든 계산대의 손님은 시간이 1씩 감소한다. 만약 0이 된 계산대가 있으면 다음 손님을 0인 계산대로 보낸다. 손님의 대기열이 비게 되면 모든 계산대의 시간이 0이 될 때까지 진행한다. (혹은 대기열이 비었을 때, 가장 길게 남은 계산대의 시간을 경과 시간에 더해도 된다.)

def queueTime(customers, n):
  xs = customers[::-1]  #고객
  tills = [0] * n    # 계산대
  elipsed = 0        # 경과시간
  while xs:
    while xs and 0 in tills:
      tills[tills.index(0)] = xs.pop()
    # 시간 보내기
    elapsed += 1
    tills = [t - 1 for t in tills]
  return elapsed + max(tills)

조금 더 간단하게

계산대를 표현하는 리스트 한 개를 준비한다. (길이는 고정됨) 다음과 같은 흐름을 생각해보자.

1. 모든 계산대 앞에는 다시 작은 대기열이 있다고 가정한다.
2. 대기열에 있는 손님은 바로 계산대 앞으로 이동하여, 앞사람의 계산을 기다린다. 이 때, 손님은 계산대 중 가장 빨리 끝날 것으로 보이는 곳으로 가서 선다.
3. 전체 계산 시간은 가장 물건 수가 많은 대기열이다.

이를 코드로 옮기면 다음과 같다.

def queueTime(customers, n):
  tills = [0] * n
  for cus in customers:
    tills[tills.index(min(tills))] += cus
  return max(tills)

이렇게 써 놓고 보니 황당할만큼 간단한 문제였넹…