[LeetCode 75] Maximum Average Subarray I

Q:

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Constraints: 1 <= k <= n <= 105

A:

처음에 짠 for문이 조건상 코너케이스가 좀 생겼는데 코너케이스 고려 못해서 에러 (k >= n - 1 인 경우)
이후 에러 좀 떠서, 코너케이스 애초에 안생기게끔 for문 조건 수정

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # max avg value -> max sum value

        result = -1e4 * 1e5 # min sum value possible

        # start idx of window: 0 ~ len(nums) - k
        # end idx of window (includes): k - 1 ~ len(nums) - 1
        for i in range(0, len(nums) - k + 1):
            start = i
            end = k - 1 + i

            # result: max sum value
            result = max(result, sum(nums[start : end + 1]))

        # result -> max avg value
        result /= k
        return result

➡ Time Limit Exceeded❌

이제 논리상 에러는 안뜨는데
긴 리스트, 큰 숫자 들어오면 시간초과 뜸

이번에도 코너케이스 애초에 안생기게 신경쓰면서 for문 작성

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        result = -1e4 * 1e5

        # time limit exceeded 해결: 중간에 겹치는 부분 더한 값 전해주기
        # 이것도 코너케이스(맨 처음, 맨 끝) 없애려면
        # 전에 앞에 걸 빼줬다고 가정하고, 지금 뒤에 걸 더해주면 되겠다
        # -> 지금 이터레이션에서는 뒤에 거만 더해주면 됨,
        # 다음 이터레이션에 넘겨주기 직전에 앞에 거를 빼서 저장하고
        temp = sum(nums[0:k-1])
        for i in range(0, len(nums) - k + 1):
            start = i
            end = k - 1 + i

            # 지금 이터레이션에서는 뒤에 거만 더해주면 됨
            temp += nums[end]
            # result: max sum value
            result = max(result, temp)
            
            # 다음 이터레이션에 넘겨주기 직전에 앞에 거를 빼서 저장하고
            temp -= nums[start]

        # result -> max avg value
        result /= k
        return result

➡ Solved✅

result 변수 초기값 설정 바꿈

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # max avg value -> max sum value
        
        temp = sum(nums[0:k-1])
        # result 초기 설정
        result = temp + nums[k - 1]
        for i in range(0, len(nums) - k + 1):
            start = i
            end = k - 1 + i

            # result: max sum value
            temp += nums[end]
            result = max(result, temp)

            temp -= nums[start]

        # result -> max avg value
        result /= k
        return result

Result:

➡ Solved✅

More:

• 애초에 코너케이스 안생기게끔 하는 게 중요하구나
  • for문: 맨 처음/마지막 이터레이션 고려 -> 웬만하면 한 for문으로 다 처리할 수 있도록, 코너케이스를 따로 빼서 처리하기보다
• 다른 사람 솔루션: 맨 처음 경우를 for문 전에 처리하고 그 이후 경우부터 for문에서 진행 -> for문 코드 더 깔끔함 -> 시간 빠름 (코드에서 호출하는 변수 Locality)
  • 코드 오히려 깔끔해지는 경우라 맨 처음 이터레이션을 for문에서 따로 빼냈지만 더 좋아보임

  class Solution:
      def findMaxAverage(self, nums: List[int], k: int) -> float:
          n = len(nums)
          s = sum(nums[:k])
          answer = s
          for i in range(k, n):
              s += nums[i]
              s -= nums[i-k]
              answer = max(answer, s)
          return answer/k