[Python] #209. Minimum Size Subarray Sum(Medium)

문제 :

이 문제는 주어진 s 숫자 값을 만들기 위한 최소 수의 개수를 구하는 문제이다.

이 문제를 해결하는 방법은 2개의 포인터를 이용해서 문제를 해결해 볼 것이다.

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l,r = 0,len(nums)+1
        sub = 0
        for i in range(len(nums)):
            sub += nums[i]
            while sub >= s:
                r = min(r, i-l+1)
                sub -= nums[l]
                l +=1
        return r if r != len(nums) + 1 else 0                         

l,r 이라는 포인터를 지정해준다. 

sub이라는 subarray의 합을 만들변수를 설정하고 nums list를 순회하며 더해준다. 

만약 sub 의 값이 s값보다 크거나 같을 경우 r값과 i-l+1값을 비교해 작은 값으로 r을 설정해준다.

i-l+1을 설정한 이유는 살펴보자.

이 문제의 예시인 [2,3,1,2,4,3]에서

s값인 7보다 커질때는 

1) sub = (2+3+1+2 ) i =3, l= 0, r= 7이다. 

   여기서 r값은  min(7,3-0+1) = 4로 설정이 된다. 즉 이 값은 값이 현재 4개가 더해졌다는 것을 의미하게 된다.

2) sub = (3+1+2+4) i = 4, l = 1, r= 4 이다.

  여기서 r값은 min(4,4-1+1) 값으로 4이 된다.

3) sub = (1+2+4), i =4 ,l = 2, r=4 이다.

   여기서 r값은 min(4,4-2+1) 값으로 3이 된다.

 

결국 r값이 의미하는 바는 sub에 몇개의 원소가 더해지는지를 의미하게 된다. 

 

결과