LeetCode-209 Minimum Size Subarray Sum 파이썬 풀이

Minimum Size Subarray Sum - LeetCode

문제

양수인 int형 배열 nums에서 target 보다 크거나 같은 값이 되기 위해선 최소한 몇개의 요소가 필요한지 계산하는 문제이다.

풀이

문제를 처음 보고 한자릿수부터 배열 길이만큼의 자릿수까지 현재 더할 수 있는 최대값을 더하면 쉽게 구할 수 있을 거라 생각했다.

1. 한자릿수부터 배열 길이만큼의 자릿수만큼 순회하는 i

2. j는 (0,i) 안에서 순회하면서 현재 더할 수 있는 가장 큰값을 더하여 sumResult에 저장한다.

3. 한번 더해진 값은 제거한다.

이런식으로 반복하면 현재 자릿수에서 얻을 수 있는 가장 큰수에 금방 도달하기 때문에 빠르게 성공할 것이라 생각했지만 오답이었다 ^^.. 

똑같은 케이스에서 계속 빠져나가지 못하고, 점점 머릿속에서도 헷갈려져서 이방법은 포기했다.

다음은 Sliding Window를 적용하여 푼 방법이다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        for i in range(1,len(nums)+1):
            j=1
            sumResult = 0
            tmp = nums.copy()
            while j < i+1:
                maxTmp = max(tmp)
                sumResult += maxTmp
                tmp.pop(tmp.index(maxTmp))

                if sumResult >= target:
                    return i
                j+=1
        return 0

SlidingWindow로 target에서 배열의 앞에 위치해 있는 요소부터 하나씩 뺀다. 이때 target의 값이 0보다 같거나 작아진다면  해당 길이를 정답으로 저장해둔다. 연속된 배열이 아니어도 되기 때문에 존재하는 또다른 배열을 찾기 위해서 startIdx를 +1 해가며 target에 더한다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        startIdx = 0
        sumResult = len(nums) + 1
        for endIdx in range(0,len(nums)):
            target -= nums[endIdx]
            while target <= 0:
                sumResult = min(sumResult, endIdx - startIdx + 1)
                target += nums[startIdx]
                startIdx += 1
        return sumResult % (len(nums) + 1)