[LeetCode] Minimum Size Subarray Sum

 

 

목차

• 문제
• 문제 풀이
  • 풀이 1 : 완전탐색
  • 풀이 2 : 개선된 완전탐색
  • 풀이 3 : 이분탐색
  • 풀이 4 : 투 포인터 사용
• 알게 된 내용
• 출처

문제

• 연속된 배열에서 특정 구간의 합이 target보다 커지는 구간 중 구간 길이가 최소인 길이를 구하는 문제입니다.
• 예시

  • Input: target = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: The subarray [4,3] has the minimal length under the problem constraint.

  • Input: target = 4, nums = [1,4,4]
    Output: 1

  • Input: target = 11, nums = [1,1,1,1,1,1,1,1]
    Output: 0

문제 풀이

풀이 1 : 완전탐색

• 풀이
  • 단순하게 모든 i~j 까지에 대해서 Sum을 계산하는 방식입니다. 
  • i, j ,sum함수 -> n^3의 시간복잡도를 가집니다.
• 코드

  • class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            answer = float('inf')
            for i in range(len(nums)):
                for j in range(i,len(nums)):
                    sum_value = 0
                    for k in range(i,j+1):
                        sum_value+=nums[k]
                    if sum_value>=target:
                        answer=min(answer,j-i+1)
                        break
            if answer==float('inf'):
                return 0
            else:
                return answer

• 시간복잡도
  • O(n^3)

풀이 2 : 개선된 완전탐색

• 풀이
  • 위 문제에서 sum 계산을 없애주기 위하여 누적합을 이용합니다.
  • sum 계산이 제거되어 O(n^2)이 됩니다.
• 코드

  • class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            answer = float('inf')
    
            sum_arr = [0 for _ in range(len(nums)+1)]
            value = 0
            for i in range(1,len(nums)+1):
                value+=nums[i-1]
                sum_arr[i]=value
            for i in range(len(nums)):
                for j in range(i+1,len(nums)+1):
                    sum_value = sum_arr[j]-sum_arr[i]
                    if sum_value>=target:
                        answer=min(answer,j-i)
                        break
            if answer==float('inf'):
                return 0
            else:
                return answer

• 시간복잡도
  • O(n^2)

풀이 3 : 이분탐색

• 풀이
  • 위 코드에서 for j in range(i,len(nums)) 부분을 이분탐색으로 변경해 주면 O(n^2)을 O(nlogn)의 시간복잡도로 줄일 수 있습니다.
• 코드

  • from bisect import bisect_left
    
    class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            answer = float('inf')
    
            sum_arr = [0 for _ in range(len(nums)+1)]
            value = 0
            for i in range(1,len(nums)+1):
                value+=nums[i-1]
                sum_arr[i]=value
    
            for i in range(len(nums)):
                # target <= sum_arr[j]-sum_arr[i]여야합니다.
                # 따라서 target+sum_arr[i]가 sum_arr[j]보다 작아야합니다.
                # 즉 bisect_left 결과 target+sum_arr[i]가 sum_arr의 j번재 인덱스에 존재해야합니다.
                left_idx = bisect_left(sum_arr,target+sum_arr[i])
                if left_idx<len(sum_arr):
                    answer = min(answer,left_idx-i)
    
            if answer==float('inf'):
                return 0
            else:
                return answer

• 시간복잡도
  • O(nlogn)

풀이 4 : 투 포인터 사용

• 풀이
  • 오른쪽 값을 하나씩 증가해 나가면서 값을 증가하다가 만약 target 값보다 그 값이 커지면 더해졌던 left값을 하나씩 제거해 봅니다.(합이 target보다 작아질 때까지) 이런 식으로 쭈욱 체크해 나가면 O(2n)만에 해결이 가능합니다.
• 코드

  • class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            left = 0
            answer = float('inf')
            sum_value = 0
            for i in range(len(nums)):
                sum_value +=nums[i]
                while sum_value>=target:
                    answer = min(answer,i-left+1)
                    sum_value-=nums[left]
                    left+=1
            if answer!=float("inf"):
                return answer
            else:
                return 0

• 시간복잡도
  • O(N)

알게 된 내용

• 특정 구간에 대한 합을 구할 때(sum함수) 매번 합을 구하는 과정을 누적합을 이용하여 그 값들의 차를 이용하면 O(N)으로 계산되던 시간복잡도를 O(1)로 줄일 수 있습니다.
• 특정 조건을 만족하는 부분을 찾기 위해서 for문을 사용할 때 for문 대신 이분탐색을 사용하면 O(N)으로 탐색하던 과정을 O(logN)만에 탐색이 가능해집니다. (이분탐색은 항상 단조증가나 단조감소처럼 규칙이 있을 때만 사용하여 시간을 줄일 수 있습니다.)
• 인접한 sub-array를 찾는 문제는 sliding window (투포인터)를 사용하여 접근해 볼 수 있습니다.

출처

• https://leetcode.com/explore/learn/card/array-and-string/205/array-two-pointer-technique/1299/