[leetcode] 643. Maximum Average Subarray I Python

해당 문제를 굉장히 헤맸다.

# time limit exceeded 3번

# wrong answer 4번

# runtime error 1번 - leetcode는 print 대신 return사용해야되는데 print 사용함

총 8번을 틀렸는데...

 

wrong answer는 총 3가지의 경우 때문에 나왔다.

(1) len(nums) <= k에서 =를 실수로 넣지 않아서

(2) update_max/k 를 update_max만 리턴해서

(3) 음수를 염두해야하는데 특정 변수의 초기값을 0으로 해놓고 코드에서 제대로 업데이트를 시켜주지 않아서

 

time limit exceeded 3번이 정말로 힘들었다.

계속 여러 번 시도해본 결과 문제는 아마도 sums를 계속 k개의 숫자만큼 계산을 n.length-(k-1)만큼 반복하게 해서 그런듯 하다.

오류의 코드는 다음과 같다.

#Time Limit Exceeded
nums_four_list = []
total = []
if len(nums) == k:
    print(sum(nums)/k)
for i in range(len(nums)-(k-1)):
    nums_four_list = nums[i:i+k]
    total.append(sum(nums_four_list))

print(max(total)/k)

#Time Limit Exceeded
initial_max_total = sum(nums[0:k])
new_max = 0
update_max = 0
if len(nums) < k:
    print(sum(nums)/k)
for i in range(len(nums)-(k-1)):
    # print(update_max)
    new_max = sum(nums[i:i+k])
    if i == 0:
        if new_max >= initial_max_total:
            update_max = new_max
            newmax = 0
    else:
        if new_max > update_max:
            update_max = new_max
            newmax = 0

print(update_max/k)

#Time Limit Exceeded
update_max = sum(nums[0:k])
new_max = -9999999
update_max = -9999999
if len(nums) <= k:
    print(sum(nums)/k)
    
for i in range(len(nums)-(k-1)):
    new_max = sum(nums[i:i+k])
    if new_max > update_max:
        update_max = new_max
    # print(update_max)

# print(update_max/k)
print(update_max/k)

 

---

 

계속 틀리다가 결국 solution을 보게 되었다.

solution에서 주는 하나의 풀이는 sums의 계산을 단 1번만 초기에 하고,

반복적으로 {

현재값과 다음 index의 값을 더한 후, 이전에 구했던 index들 중 가장 초기값을 빼는 것 ----- (a)

그리고 이렇게 구한 이전의 max값과 (a)의 결과를 max를 통해 구한 후,

이를 best값으로 정한다.

}

© https://leetcode.com/problems/maximum-average-subarray-i/solution/

## solution
best = 0
now = sum(nums[0:k])
best = now
for i in range(k,len(nums)):
    now += nums[i] - nums[i-k]
    best = max(best,now)
print(best/k)

 

확실히 solution을 보니 time limit exceeded가 나온 나의 코드보다 훨씬 계산이 줄어들었다는 것을 깨달았다.

이런 형태를 아마 "sliding window"라고 하는 듯하다.

이런 문제해결 방법은 아예 생각을 하지 못했으니 후회는 없지만,

확실히 아쉽다는 생각이 든다.

 

 

출처: https://leetcode.com/problems/maximum-average-subarray-i/

Maximum Average Subarray I - LeetCode