[알고리즘/Python] LeetCode 209. Minimum Size Subarray Sum

📑 1. 문제 이해

https://leetcode.com/problems/minimum-size-subarray-sum/?envType=study-plan-v2&envId=top-interview-150

Minimum Size Subarray Sum - LeetCode

 배열의 부분 집합들 중 그 합이 target보다 크거나 같은 부분 집합 중 가장 짧은 길이를 구하는 문제입니다. 배열의 원소는 모두 양수이며, 배열은 정렬되어 있지않고 중복된 원소가 있을 수 있습니다.

☑️ 테스트케이스

문제에서 주어진 테스트케이스는 다음과 같습니다.

 

1) Example1: target = 7, nums = [2, 3, 1, 2, 4, 3]

   - 합이 target이 되는 부분집합이 배열의 끝에 위치합니다.

2) Example2: target = 4, nums = [1, 4, 4]

    - target과 값이 같은 원소가 여러개 존재합니다.

3) Example3: target =11, nums = [1, 1, 1, 1, 1, 1, 1, 1]

   - 전체를 다 더해도 target보다 작습니다.

 

추가로 생각해볼 테스트케이스는 다음과 같습니다.

 

4) target =15, nums = [1, 2, 3, 4, 5]

    - 전체를 다 더하면 target이 됩니다.

5) target 3, nums = [1]

   - 배열의 길이가 1이고, 전체 합이 target보다 작습니다.

💡 2. 알고리즘 설계

 최소 길이의 부분 집합을 구하기 위해서는 부분집합의 처음과 끝을 포인터로 가리켜서 부분집합을 나타내는 윈도우를 설정한후 윈도우를 옮기며 조건을 만족하는 부분집합이 있는지 확인하는 슬라이딩 윈도우를 떠올릴 수 있습니다.

  이때 길이가 1인 슬라이딩 윈도우부터 점차 크기를 늘려가며 윈도우 내 원소의 합이 target보다 크거나 같은 경우가 존재하는지 확인합니다. 조건을 만족하는 경우 그때의 윈도우의 크기가 조건을 만족하는 부분집합들 중 최소이므로 그 길이를 반환합니다.

 

1. 처음 윈도우의 크기를 1로 설정합니다. 이때 윈도우의 처음을 나타내는 포인터 left를 0, 윈도우의 끝을 나타내는 포인터 right를 윈도우의 사이즈로 초기화합니다. 윈도우는 left를 포함하고 right를 포함하지 않습니다.

2. 윈도우 내부의 원소의 합을 구합니다.

3. 슬라이딩 윈도우를 한칸씩 오른쪽으로 움직이면서 원소의 합이 target보다 크거나 같은 경우가 있는지 확인합니다. 이때 원소의 합을 새로 구하는 것이 아니라 빠진 원소의 값을 빼고, 새로 들어온 원소의 값을 더해서 구함으로서 중복된 연산을 방지합니다. 

4. 만약 원소의 합이 target보다 크거나 같은 부분집합이 존재한다면 그 사이즈를 반환합니다.

5. 발견하지 못했다면 윈도우 사이즈를 1 늘려 다시 처음부터 탐색합니다.

def solution(target: int, nums: List[int]) -> int:
    for size in range(1, len(nums) + 1):
        left = 0
        right = size
        sub_sum = sum(nums[i] for i in range(size))
        while sub_sum < target and right < len(nums):
            sub_sum -= nums[left]
            sub_sum += nums[right]
            left += 1
            right += 1

        if sub_sum >= target:
            return size
    return 0

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N^2). 부분집합의 합을 계산하는 연산은 O(N)  복잡도를 가집니다. 슬라이딩 윈도우의 크기는 1부터 N이 될 수 있고 각 크기별로 배열의 처음부터 끝까지 탐색하므로  O(N^2) 시간 복잡도를 가집니다. 따라서 총 시간 복잡도는 가장 높은 차수를 기준으로 O(N^2)이 됩니다. 배열의 길이가 최대 10,000으로 최대 연산 횟수가 100,000,000이 되어 Time Limit Exceeded 에러가 발생합니다. 

공간 복잡도: O(N). 부분집합의 합을 계산하기 위한 리스트 comprehensing 문법에 의해 최대 n 길이의 iterator가 생성됩니다. 

 

⚒️ 3. 최적화

부분집합의 크기를 가장 큰 경우부터 점차 크기를 줄여가면 제한시간 내에 실행이 완료됩니다. 크기가 큰 부분집합부터 확인을 할때, 그 크기의 부분집합 중 원소의 합이 target이 되는 경우가 없다면 더 작은 부분집합 중에도 조건을 만족하는 부분집합이 존재할 수 없습니다. 따라서 조기에 반복문을 종료하여 불필요한 작업을 하지 않을 수 있습니다. 만약 작은 크기의 윈도부터 확인한다면 조건을 만족하는 부분집합이 없는 경우에도 O(N^2) 연산을 모두 수행하지만, 큰 크기의 윈도우 부터 확인한다면 첫번째 for문에서 (window 사이즈 = 배열의 길이) for문이 종료됩니다.

    total = sum(nums)
    min_window_size = 0

    for size in range(len(nums), 0, -1)):
        left = 0
        right = size
        sub_sum = total - sum(nums[i] for i in range(right, len(nums)))

        while sub_sum < target and right < len(nums):
            sub_sum -= nums[left]
            sub_sum += nums[right]
            left += 1
            right += 1

        if sub_sum >= target:
            min_window_size = size
        else:
            break
            
    return min_window_size

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N^2). 여전히 시간복잡도는 O(N^2)입니다. 최악의 경우 조건을 만족하는 부분집합의 크기가 1이라면 O(N^2)연산이 모두 수행됩니다. 제출이 Accept되지만 실행시간이 7471ms로 매우 느립니다. 

공간 복잡도: O(N). 부분집합의 합을 계산하기 위한 리스트 comprehensing 문법에 의해 최대 n 길이의 iterator가 생성됩니다. 

 

---

🤔 다른 사람의 풀이

위의 슬라이딩 윈도우 알고리즘이 통과는 되지만 실행 시간이 매우 느려 부족한 답변임을 알 수 있습니다. 마찬가지로 슬라이딩 윈도우를 사용하지만 불필요한 연산을 줄여 훨씬 빠른게 수행할 수 있음을 알게되었습니다. 위 풀이에서 불필요한 연산은 1) 매번 부분집합의 합을 계산하는 것과 2) 최소 크기 이상의 윈도우도 검사하게 된다는 점입니다. 

 

 이 풀이에서는 r 즉, 배열의 오른쪽 끝(inclusive)을 기준으로 조건을 만족하는 윈도우가 있는지 확인하는데 이때, 앞에서 발견된 최소 윈도우크기를 기준으로 합니다. 즉 앞에서 길이가 2이면서 조건을 만족하는 윈도우가 발견되었다면, 현재 r을 기준으로 길이가 2인 윈도우가 조건을 만족하는지 확인합니다. 조건을 만족한다면 더 작은 윈도우가 조건을 만족하는지 크기를 줄여가며 확인합니다. 더 작은 윈도우가 조건을 만족한다면 그 윈도우 크기를 기준으로 탐색을 이어갑니다.

 

1. 최소 윈도우 크기를 담는 변수 minlen을 무한대로 초기화합니다. 이는 불가능한 값으로 초기화하여, 조건을 만족하는 부분집합이 발견되지 않아 minlen값이 한번도 갱신되지 않는다면 0을 반환하기 위합니다.

2. 윈도우의 왼쪽 포인터를 의미하는 l과 윈도우 내부 원소들의 합을 의미하는 sum을 0으로 초기화합니다.

3. 윈도우의 오른쪽 포인터를 의미하는 r을 오른쪽으로 한칸씩 옮겨가며 오른쪽 포인터가 r일때 조건을 만족하는 최소 윈도우를 찾습니다.

    - 윈도우 포인터가 오른쪽으로 한칸 이동하면  새로운 원소가 윈도우 내부로 들어온 것으로 sum에 더해줍니다.

    - 만약 현재 윈도우가 조건을 만족한다면 minlen값을 갱신해주고 왼쪽 포인터를 한칸 오른쪽으로 옮깁니다. 이때 매번 기존의 minlen값과 비교하여 더 작을 경우에만 갱신해주어야합니다. 

  - 윈도우가 더 이상 조건을 만족하지 않으면 while문을 종료합니다.

4. 최소 윈도우 크기 minlen를 반환합니다. 만약 minlen이 여전히 float('inf')라면 조건을 만족하는 부분집합이 없다는 의미이므로 0을 반환합니다.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minlen = float('inf')
        l,sum =0,0
        for r in range(len(nums)):
            sum += nums[r]
            while sum >= target:
                minlen = min(minlen, r-l+1)
                sum -= nums[l]
                l += 1
        return minlen if minlen<=len(nums) else 0

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 최악의 경우 배열의 각 원소를 두번씩 방문하게 됩니다(오른쪽 포인터에 의해 한번, 왼쪽 포인터에 의해 한번). 실제로 실행시간이 7471ms -> 253ms로 약 1/30로 줄어들었음을 알 수 있습니다.

공간 복잡도: O(1). 변수를 제외한 별도의 배열을 위한 공간이 필요하지 않습니다.

 ⎌ 4. 검토

테스트 케이스를 살펴보면 다음과 같습니다.

 

2) Example2: target = 4, nums = [1, 4, 4]

     - l = r = 1일때 조건을 만족하므로 minlen =1로 갱신되고 그 값이 반환됩니다. 이 후에도 [4,4], [4]가 조건을 만족하지만 윈도우의 길이가 minlen과 같거나 더 크므로 minlen은 갱신되지 않습니다.

 

3) Example3: target =11, nums = [1, 1, 1, 1, 1, 1, 1, 1] 5) 와 5) target = 3 nums = [11]의 경우

    - r이 배열 끝까지 도달할때까지 한번도 sum >= target을 만족하지 않으므로 minlen은 여전히 float('inf')가 되어 0이 반환됩니다.

 

4) target =15, nums = [1, 2, 3, 4, 5]

    - r이 배열의 끝까지 도달하고 나서 sum = target이 되므로 minlen이 갱신됩니다. 그 이후 왼쪽 포인터를 오른쪽으로 이동할 수 없으므로 반복문이 종료됩니다. 

---

✅ 정리

◎ 배열에 대하여 슬라이딩 윈도우를 사용시 모든 윈도우 크기에 대해서 검사해봐야하는 경우 O(N^2) 시간 복잡도를 가지게 될 수 있습니다. 이때는 불필요한 연산(이미 나온 결과보다 덜 최적화 된 해) 혹은 중복된 연산을 줄일 수 있어야합니다.