문제 개요
customers라는 배열이 있다고 가정해 보겠습니다. 각 원소 customers[i]는 [arrival_i, time_i] 형태의 쌍을 담고 있으며, arrival_i는 i번째 고객의 도착 시간, time_i는 해당 고객의 주문을 준비하는 데 걸리는 시간을 의미합니다. 도착 시간은 오름차순으로 정렬되어 있습니다.
고객이 도착하면 바로 주문을 하지만, 실제 조리는 요리사가 한가할 때만 시작됩니다. 요리사는 동시에 여러 명의 음식을 준비할 수 없으며, 주문이 접수된 순서대로 처리합니다. 우리의 목표는 모든 고객의 평균 대기 시간을 구하는 것입니다.
예시로 이해하기
입력이 customers = [[7,2],[8,4],[10,3],[20,1]]이라면 출력은 3.5가 됩니다. 그 이유를 단계별로 살펴보겠습니다.
첫 번째 고객: 시각 7에 도착했습니다. 요리사가 놀고 있으므로 즉시 조리를 시작해 시각 9에 완성됩니다. 대기 시간은 9 − 7 = 2입니다.
두 번째 고객: 시각 8에 도착했습니다. 첫 번째 주문이 진행 중이므로 시각 9에 조리가 시작되고 시각 13에 완성됩니다. 대기 시간은 13 − 8 = 5입니다.
세 번째 고객: 시각 10에 도착했습니다. 앞선 주문이 끝나는 시각 13에 조리가 시작되고 시각 16에 완성됩니다. 대기 시간은 16 − 10 = 6입니다.
네 번째 고객: 시각 20에 도착했습니다. 요리사가 놀고 있으므로 즉시 조리를 시작해 시각 21에 완성됩니다. 대기 시간은 21 − 20 = 1입니다.
따라서 평균 대기 시간 = (2 + 5 + 6 + 1) / 4 = 3.5입니다.
풀이 접근 방법
핵심 아이디어는 간단합니다. 지금까지 누적된 '조리 종료 시각'을 추적하면서 각 고객의 주문이 언제 끝나는지 계산하고, 여기서 도착 시각을 빼면 대기 시간이 됩니다.
- arr := 새 리스트 생성
- time := 0 (현재 조리 가능 시각)
- customers의 각 쌍 (i, j)에 대해 다음을 수행합니다.
- i > time이면(고객이 늦게 도착해 요리사가 놀고 있는 경우): time := i + j
- 그렇지 않으면(주문이 밀려 있는 경우): time := time + j
- arr의 끝에 (time − i), 즉 대기 시간을 추가합니다.
- arr에 담긴 값들의 평균을 반환합니다.
구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(customers):
arr = []
time = 0
for i , j in customers:
if(i > time):
time = i + j
else:
time += j
arr.append(time - i)
return sum(arr) / len(arr)
customers = [[7,2],[8,4],[10,3],[20,1]]
print(solve(customers))입력
[[7,2],[8,4],[10,3],[20,1]]
출력
3.5
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 효율적으로 동작합니다. 고객 수가 많아지더라도 안정적으로 평균 대기 시간을 계산할 수 있습니다.