[2024] day 192. Leetcode 1701. Average Waiting Time

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 7월 9일 (화)
Leetcode daily problem

1701. Average Waiting Time

https://leetcode.com/problems/average-waiting-time/

Problem

1인 셰프가 있는 레스토랑에 customers[i] = [arrivali, timei]인 배열이 주어진다.

arrivali는 i번째 고객의 도착 시간이고, 도착 시간은 내림차순으로 정렬되지 않았다. timei는 i번째 고객의 주문을 준비하는 데 필요한 시간이다.

고객이 도착하면 셰프에게 주문을 하고, 셰프는 자리가 나면 음식 준비를 시작합니다. 고객은 요리사가 주문 준비를 마칠 때까지 기다린다. 셰프는 한 번에 한 명 이상의 고객을 위한 음식을 준비하지 않는다. 요리사는 입력된 순서대로 고객을 위해 음식을 준비한다.

모든 고객의 평균 대기 시간을 반환한다.

Solution

simulation (시뮬레이션)

각 고객의 대기 시간은 '고객이 음식을 받은 시간 - 고객의 도착 시간' 이다. 각 고객에 대해 도착한 시간과 현재 시간을 비교해서 현재 시간과 고객의 도착 시간 중 더 큰 값을 사용해 음식을 준비한다.
음식을 준비하는 데 걸리는 시간을 더해 고객이 음식을 받는 시간을 계산한다.
그 후 고객의 대기 시간을 계산해서 총 대기 시간에 더하고, 현재 시간을 업데이트 한다.

모든 고객의 대기 시간을 더한 후 고객 수로 나눠서 평균 대기 시간을 구한다.

Code

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        cur_time = 0
        wait_time = 0
        
        for customer in customers:
            cur_time = max(cur_time, customer[0]) + customer[1]
            wait_time += cur_time - customer[0]
            
        return wait_time / len(customers)
        

Complexicity

시간 복잡도

주어진 customers 배열을 한 번 순회하므로 시간 복잡도는 O(n) 이다. 배열을 순회하면서 상수 시간의 업데이트를 하므로 최종 시간 복잡도는 O(n)이다.

공간 복잡도

현재 시간과 고객이 기다리는 상수 변수만 업데이트 되므로 공간 복잡도는 O(1) 이다.