LeetCode 1701. Average Waiting Time 자바 문제 풀이

문제 설명

• 문제: https://leetcode.com/problems/average-waiting-time/
• 설명: 각 고객의 도착 시간과 요리 시간을 고려하여 모든 고객의 평균 대기 시간을 구하는 문제입니다. 각 고객은 이전 고객의 요리가 끝난 후에 요리를 시작할 수 있습니다.

접근 방식

• 아이디어:
  • 요리시간은 언제나 현재 시간에 더해집니다. 손님이 늦게 도착하든 빠르게 도착하든 소모됩니다.
  • 현재 시간이 고객의 도착 시간보다 작다면, 현재 시간을 고객의 도착 시간으로 업데이트합니다.
  • 고객의 도착 시간과 요리 시간이 주어지므로, 고객이 도착한 이후 요리가 끝날 때까지 걸리는 시간을 계산하여 총 대기 시간에 더합니다.
• 알고리즘:
  1. totalWaitTime과 currentTime 변수를 초기화합니다.
  2. 각 고객에 대해 다음을 수행합니다:
     • 현재 시간이 고객의 도착 시간보다 작으면 현재 시간을 고객의 도착 시간으로 업데이트합니다.
     • 현재 시간에 요리 시간을 더하여 요리가 끝나는 시간을 계산합니다.
     • 요리가 끝나는 시간에서 고객의 도착 시간을 뺀 값을 총 대기 시간에 더합니다.
     • 현재 시간을 요리가 끝나는 시간으로 업데이트합니다.
  3. 총 대기 시간을 고객 수로 나누어 평균 대기 시간을 반환합니다.

코드

class Solution {
    public double averageWaitingTime(int[][] customers) {
        int n = customers.length;
        long totalWaitTime = 0;
        long currentTime = 0;

        for (int[] customer : customers) {
            int arrivalTime = customer[0];
            int cookingTime = customer[1];

            if (currentTime < arrivalTime) {
                currentTime = arrivalTime;
            }

            currentTime += cookingTime;
            totalWaitTime += (currentTime - arrivalTime);
        }

        return (double) totalWaitTime / n;
    }
}

결론

• 시간 복잡도:
  • 이 알고리즘은 각 고객을 한 번씩 순회하므로 O(n)의 시간 복잡도를 가집니다.
• 공간 복잡도:
  • 추가적인 공간을 거의 사용하지 않으므로 O(1)의 공간 복잡도를 가집니다.