(간단한 코드)리트코드 643. Maximum Average Subarray I

 

이 문제는 "슬라이딩 윈도우"라고 부르는 문제다. 

 

슬라이딩 윈도우는 딥러닝에서 정말로 자주 나오는 용어이며, 이는 통계학에서도 유래한 것으로 알고 있다(아닐 수도)

 

k길이 만큼으로 리스트 안에 있는 숫자들을 더하고 평균을 구한 값들 중에서 가장 큰 수를 반환하면 된다.

이런 방식은 통계학에서 moving average(이동 평균)이라고 하며, 데이터의 추세를 파악하는데 사용된다.

 

코드는 다음과 같다

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        n = len(nums)
        cur_sum = 0

        for i in range(k): # 이부분은 k가 고정된 숫자가 아니므로, 처음에는 이렇게 별도로 해준다.
            cur_sum += nums[i]
        
        max_avg = cur_sum / k
		# 여기서 리스트에 모든 평균 숫자를 저장하는게 아니라,
        # cur_sum을 계속해서 바꿔 나가는 형식을 취할 것이다.
        # 그 이유는, 리스트 안에 숫자량이 방대한 것이 있어, 통과가 안되기 때문이다.
        
        for i in range(k,n): #k번 부터 시작, n-1번 까지 
            cur_sum += nums[i] # 다음 숫자를 더하기
            cur_sum -= nums[i-k] # 이전 숫자에서 가장 앞에 있는 숫자를 빼기

            avg = cur_sum / k
            max_avg = max(max_avg,avg) # 더 큰 숫자로 업데이트
        
        return max_avg

 

보기 편하게 하기 위해 따로 쓴 것이지만, 다음과 같이 간략하게도 할 수 있다.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        n = len(nums)
        cur_sum = sum(nums[0:k]) # 가장 앞의 k개의 합
        res = cur_sum #cur_sum은 계속해서 수치가 바뀌므로, 그 전의 수치를 저장하는 변수

        for i in range(k,n):
            cur_sum += nums[i] - nums[i-k] #더하고 빼기를 동시에 해줌
            res = max(res, cur_sum) #큰 것으로 업데이트

		return res / k #평균을 반환