[리트코드/leetcode/python] 209. Minimum Size Subarray Sum

이미지를 누르면 문제 링크를 보실 수 있습니다

처음에 그냥 생각나는 로직대로 푼 알고리즘은 다음과 같습니다. nums를 처음부터 더하는데, target보다 같거나 커지면, check 변수를 통해 플래그를 걸어 놓고 여태 더했던 순회 횟수, 즉 길이를 저장합니다. 

그리고 다음 인덱스로부터 또 같은 행동을 반복하는데, 최소 길이가 갱신 된다면 최소 길이를 갱신하고 그렇지 않다면 그냥 패스합니다.

풀었던 코드는 아래와 같습니다. 

 

푼 코드는 아래와 같습니다.

class Solution(object):
    def minSubArrayLen(self, target, nums):

        for i in range(len(nums)):
            
            tmp = 0

            for j in range(i,len(nums)):
            
                tmp += nums[j]

                if tmp >= target :
                    
                    length = j-i + 1

                    if length <= answer:
                        check = True
                        answer = length

        if check == False:
            answer = 0

        return answer

하지만, 해당 코드는 시간초과를 발생시켰고, 문제를 통과하기에는 알고리즘을 개선했어야 했습니다.

구글링을 하다가 좋은 래퍼런스를 발견해서 공유해보겠습니다.

https://janac.medium.com/what-is-the-sliding-window-algorithm-f9fcfe92b853

What Is The Sliding Window Algorithm?

해당 글에서는 sliding window 알고리즘이 무엇인지에 대해 설명하고 있는데, "Maximum Sum of SubArray" 뿐만 아니라 "Smallest Subarray with Sum K" 도 배울 수 있을겁니다!

 

키포인트는 그림을 통해 설명해드리겠습니다.

윈도우 크기가 3이라고 치고 처음부터 출발하면, [4,2,1] 을 더하면 7 이 나옵니다.

다음 인덱스로부터 출발할 때, 또 다시 윈도우 크기가 3개니까 [2,1,7]을 더하면 10이 나오는데요,

여기서 [2,1]은 공통이고 맨 처음원소가 빠지고 새로운 원소를 더해줌으로써 10이 만들어진 셈입니다.

즉, 중복해서 또 다시 1과 2를 더하는 불필요한 작업을 피할 수 있다는 것입니다.  

 

그렇다면, "Smallest SubArray with Sum K"에서도 똑같은 생각을 해봅시다.

하나씩 더해가면서 누적합이 target보다 같거나 크다면, check 변수를 통해 플래그를 걸어주고, 최소 윈도우 크기를 갱신합니다. 이 때, 누적합에서 최초로 들어간 수를 빼주고, 윈도우 시작 원소 인덱스를 1 증가함으로써 나머지 수는 중복해서 더하지 않고 target과 누적합을 비교할 수 있습니다.

첫 번째 원소를 뺐는데도, 여전히 target보다 같거나 크다면, 계속해서 target에 가까워지는 만큼 최소 윈도우 크기를 갱신해 나가고, 그에 따라 윈도우 시작 인덱스도 계속해서 증가시킵니다. 이렇게 하면, 시간복잡도가 많이 줄어들게 됩니다.

 

코드는 아래와 같습니다.

class Solution(object):
    def minSubArrayLen(self, target, nums):
    
        window_start = 0
        minimum_window = len(nums)
        running_window_sum = 0 
        check = False

        for i in range(len(nums)):
            
            running_window_sum += nums[i]

            while running_window_sum >= target:
                check = True
                minimum_window = min(minimum_window, i-window_start+1)
  
                running_window_sum -= nums[window_start]     
                window_start += 1

        if check == True:
            return minimum_window
        else:
            return 0

이상으로 Minimum Size Subarray Sum 문제를 정리해봤습니다.