Leetcode 2090. K Radius Subarray Averages

https://leetcode.com/problems/k-radius-subarray-averages/description/

K Radius Subarray Averages - LeetCode

문제

0부터 시작하는 정수가 포함되어있는 배열 nums와 정수 k가 주어진다.

 

k-radius average는 index i를 중심으로 k만큼(i - k ~ i + k)의 반지름을 가진 부분배열의 평균을 뜻한다. 만약 엘레멘트의 갯수가 k보다 작거나 반지름의 범위가 배열의 범위를 벗어나는 경우에는 k-radius average는 -1이 된다.

 

위의 조건에 해당하는 array를 만들고 각 index에 맞는 k-radius average의 값을 넣어 반환하라

 

또한 평균의 경우 x개수의 엘레멘트의 합을 x의 갯수로 나눈 것을 뜻하며 이 때 정수미만은 절삭하는 integer division(정수 나눗셈)을 이용해 평균을 구하면 된다.

 

예를 들어 2, 3, 1, 5의 정수 나눗셈의 경우 ( 2 + 3 + 1 + 5 ) / 4 = 11 /  4 = 2.75 이지만 정수 미만은 절삭하는 정수 나눗셈이기 때문에 평균은 2가 된다.

 

코드

class Solution:

    def getAverages(self, nums: list[int], k: int) -> list[int]:

        l = len(nums)

        answer = [-1] * l

        size = 2 * k + 1

        s = sum(nums[:k * 2])

        # if l < k:

        #     return answer

       

        # if k == 0:

        #     return nums

       

        # # i + k => 중심점

       

        # for i in range(l - 2 * k):

        #     answer[i + k] = sum(nums[i : i + 2 * k + 1]) // (2 * k + 1)

       

        for i in range(2 * k, l ):

            s += nums[i]

            answer[i - k] = s // size

            s -= nums[i - k * 2]

           

        return answer

       

---

문제를 읽을 때 부터 O(n)으로 만족해야 겠구나 라는 생각으로 문제를 시작했다. 주석 처리되어 있는 코드는 각 범위를 구한 뒤  그 범위에 해당하는 배열을 복사해 정답 배열에 넣는 형식으로 진행했아느 시간 초과가 발생했다. 이에 유효한 평균을 구할 수 있는 범위를 구한 후 그 범위에 벗어나는 값은 빼고 추가되는 값은 더하면서 각 평균을 계산해 정답을 얻을 수 있었다.