Minimum Size Subarray Sum

Q: Minimum Size Subarray Sum의 시간 복잡도는 얼마인가요?

슬라이딩 윈도우 풀이의 시간 복잡도는 O(n) 이고 공간 복잡도는 O(1) 입니다. 내부 반복문 때문에 시간 복잡도가 이차 시간이 될 것처럼 보이지만, left 는 앞으로만 이동하므로 전체 실행 동안 최대 n 번 이동합니다. 접두사 합 버전의 시간 복잡도는 O(n log n) 이고, 모든 시작 위치를 확인하는 방법의 시간 복잡도는 O(n²) 입니다.

Q: O(n) 풀이가 있는데 왜 O(n log n) 누적 합 풀이를 배울까요?

면접관은 O(n) 답변 다음에 이 방법을 자주 물어봅니다. 이는 양수 값의 또 다른 활용법을 보여 줍니다. 접두사 합이 정렬되어 있으므로 이진 검색을 통해 누적 합이 임계값을 처음 넘어서는 위치를 찾을 수 있습니다. 이 기법은 가중치에 비례해 무작위로 인덱스를 선택하는 문제와 같은 다른 문제에서도 다시 쓰입니다.

Q: 부분 배열의 합이 정확히 target과 같아야 하나요?

아니요. target 이상인 모든 합이 해당됩니다. target = 15 일 때, 9, 3, 7로 이루어진 윈도우의 합은 19이고 길이는 여전히 3입니다. 정확히 같은 합이 필요하다면, 양수 값에 대해서는 윈도우가 여전히 작동합니다. 합이 목표값보다 클 동안 윈도우를 줄이고, 합이 같을 때만 길이를 기록하세요.

보통슬라이딩 윈도우 누적 합

+10

양의 정수 target과 양의 정수 배열 nums가 주어집니다. 합이 target 이상인 가장 짧은 부분 배열(서로 이웃한 원소들의 연속 구간)을 찾아 그 길이를 반환하세요. target에 도달하는 부분 배열이 없으면 0을 반환하세요.

함수

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: 부분 배열의 합이 도달하거나 초과해야 하는 값
numsinteger-array: 양의 정수 배열
반환값integer: 합이 target 이상인 가장 짧은 부분 배열의 길이 또는 해당 배열이 없으면 0

제약 조건

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

예제

입력: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
출력: 3
설명: 인접한 두 수의 합은 15에 도달하지 않습니다. 가장 큰 쌍의 합은 9 + 3 = 12입니다. 세 수를 더하면 도달합니다. 4 + 2 + 9 = 15이고 9 + 3 + 7 = 19이므로 답은 3입니다.

제출 시 숨은 테스트 +16개

후속 질문

nums에 0과 음수도 포함될 수 있어 슬라이딩 윈도우가 더 이상 작동하지 않는다면 어떻게 해결하시겠어요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

값이 모두 양수이므로 부분 배열을 확장하면 합이 항상 증가하고, 자르면 항상 감소합니다. 이 한 가지 사실이 두 가지 빠른 풀이의 핵심입니다. 누적 합은 정렬된 목록이 되므로 이진 탐색을 통해 합이 처음으로 target에 도달하는 위치를 찾을 수 있습니다. 더 나아가 시작 위치가 오른쪽으로 이동해도 최적의 끝 위치는 왼쪽으로 이동하지 않으므로, 오른쪽으로 늘리고 왼쪽으로 줄이는 하나의 윈도우로 한 번의 순회만으로 답을 찾을 수 있습니다.

모든 시작 지점에서 확장하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

시작 인덱스를 정하고 오른쪽으로 이동하며 값을 하나씩 더합니다. 누적 합이 처음으로 target에 도달하면 해당 시작점에서 시작하는 가장 짧은 부분 배열을 찾은 것입니다. 더 짧은 부분 배열은 그보다 일찍 끝나며 합이 여전히 너무 작기 때문입니다. 그러므로 길이를 기록하고, 더 이상 확장하지 않은 채 다음 시작점으로 이동합니다. 정답은 모든 시작점에서 구한 길이 중 가장 작은 값입니다.

target = 15이고 [4, 2, 9, 3, 7, 1, 5]일 때, 시작점 0의 합은 4, 6, 15이며 길이 3에서 멈춥니다. 시작점 1의 합은 2, 11, 14, 21이며 길이 4에서 멈춥니다. 시작점 2의 합은 9, 12, 19이며, 다시 길이 3입니다. 어떤 시작점에서도 이보다 짧은 길이를 찾지 못합니다.

목표값에 도달하기 어려울 때 문제가 생깁니다. 어떤 부분 배열도 목표값에 도달하지 못하면 모든 시작점에서 배열의 끝까지 진행합니다. 이때 덧셈 횟수는 n(n+1)/2이며, n = 2 × 10^4일 때 2 × 10^8번입니다. 또한 각 시작점에서 이전 시작점이 이미 계산한 합을 다시 계산합니다.

알고리즘

best를 0으로 설정합니다. 아직 찾은 것이 없다는 뜻입니다.
각 시작 인덱스에 대해 누적 합을 0으로 설정합니다.
끝 인덱스를 시작 위치에서 오른쪽으로 이동하면서 nums[end]를 합계에 더합니다.
합계가 target에 도달하면 end-start+1이 best보다 크면 이를 저장하고, 이 시작 위치에서 더 이상 확장하지 않습니다.
best를 반환합니다.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

누적 합과 이진 탐색

핵심 아이디어

prefix[k]를 처음 k개 값의 합이라고 하고, prefix[0] = 0이라고 합시다. 그러면 nums[start..end-1]의 합은 prefix[end] - prefix[start]입니다. 고정된 start에 대해 prefix[end] ≥ prefix[start] + target을 만족하는 가장 작은 end를 찾으면 됩니다.

모든 값이 양수이므로 prefix는 엄격히 증가하며, 특정 값 이상이 되는 첫 위치는 이진 탐색으로 찾을 수 있습니다. [4, 2, 9, 3, 7, 1, 5]의 경우 prefix는 [0, 4, 6, 15, 18, 25, 26, 31]입니다. start가 2일 때 필요한 값은 6 + 15 = 21입니다. 21 이상인 첫 번째 prefix 값은 인덱스 5의 25이므로, 구간은 nums[2..4] = 9, 3, 7이며 길이는 3입니다.

prefix[n]조차 어떤 start에 필요한 값보다 작다면, 그 start에 대해 유효한 end는 없으며, 이후 start에 대해서도 마찬가지입니다. prefix[start]는 계속 증가하기 때문입니다. 여기서 탐색을 멈춥니다. 이 방법은 n번의 이진 탐색으로 O(n log n) 시간이 걸리고, prefix 배열에 O(n)이 추가로 필요합니다. 비교되는 최댓값은 2 × 10^8 + 10^9이며, 32비트 정수에 들어갑니다.

알고리즘

길이가 n+1인 prefix를 만들고, prefix[k+1] = prefix[k] + nums[k]로 설정합니다.
각 시작 위치에 대해 need = prefix[start] + target을 계산합니다.
prefix[n] < need이면 중단합니다. 이후 시작 위치에서는 성공할 수 없습니다.
start+1부터 n까지의 위치에서 prefix[end] ≥ need를 만족하는 첫 번째 end를 이진 탐색하고, 지금까지의 최솟값이면 end-start를 저장합니다.
가장 짧은 길이를 반환하고, 성공한 시작 위치가 없으면 0을 반환합니다.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

슬라이딩 윈도우

핵심 아이디어

윈도우 nums[left..right]와 그 합을 유지합니다. right를 한 번에 한 단계씩 이동하고 새 값을 더합니다. 합이 target 이상인 동안 윈도우는 후보입니다. 길이를 기록한 다음 nums[left]를 빼고 left를 앞으로 이동하여 더 짧은 윈도우도 여전히 조건을 만족하는지 확인합니다.

left는 왜 영원히 윈도우에서 빠져도 될까요? 윈도우 nums[left..right]의 합이 처음으로 target에 도달했을 때, 더 작은 윈도우 nums[left..right-1]의 합은 목표에 도달하지 못했습니다. 이전 단계에서 조건을 만족했다면 루프가 윈도우를 줄였을 것이기 때문입니다. 따라서 이 시작 위치에서 right는 가장 이른 끝 위치이며, 끝 위치가 더 뒤로 갈수록 더 긴 부분 배열만 만들어집니다. 이 시작 위치에서 얻을 수 있는 최선의 답은 이미 나왔습니다. 이 논리는 양수 값일 때만 성립합니다. 음수가 있으면 윈도우가 더 길어지면서 나중에 합이 더 커질 수 있습니다.

target = 15이고 [4, 2, 9, 3, 7, 1, 5]인 경우: 합은 4, 6, 15로 증가하므로 길이 3을 기록하고 4를 뺍니다(11). 3을 더하면 14가 되고, 7을 더하면 21이 됩니다. 길이 4를 기록하고 2를 뺍니다(19). 길이 3을 기록하고 9를 뺍니다(10). 1과 5를 더하면 16이 됩니다. 길이 4를 기록하고 3을 뺍니다(13). 답은 3입니다.

while 루프는 for 루프 안에 있지만, 각 인덱스는 윈도우에 한 번 들어오고 한 번 나가므로 전체 작업은 O(n)입니다. 숫자는 세 개만 저장하므로 공간 복잡도는 O(1)입니다.

알고리즘

left = 0, total = 0, best = 0으로 설정합니다.
각 right에 대해 nums[right]를 total에 더합니다.
total ≥ target인 동안, right-left+1이 best보다 크면 best를 갱신하고, nums[left]를 빼고 left를 오른쪽으로 한 칸 이동합니다.
합이 target에 도달한 적이 없다면 여전히 0인 best를 반환합니다.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

함정과 경계 사례

대부분의 버그는 윈도우를 줄이는 단계와 target에 도달하는 경우가 없을 때 반환하는 값에서 발생합니다.

while 대신 if로 윈도우를 줄이는 경우입니다. target = 12이고 배열이 [1, 1, 2, 3, 12]일 때 12를 더하면 합은 19가 됩니다. if는 길이 5를 기록한 뒤 값 하나를 제거하고 넘어가므로, 길이가 1인 윈도우 [12]는 측정되지 않습니다. 합이 여전히 충분한 동안 계속 제거하려면 루프를 사용해야 합니다.
nums[left]를 제거한 뒤 길이를 기록하는 경우입니다. 측정해야 하는 윈도우는 합이 target에 도달한 윈도우입니다.
≥ 대신 >로 비교하는 경우입니다. 합이 target과 같은 부분 배열도 포함됩니다. target = 9일 때 [3, 3, 3]의 답은 0이 아니라 3입니다.
센티널 값을 반환하는 경우입니다. best를 n+1이나 무한대로 시작했다면, target에 도달하는 경우가 없을 때 0으로 변환하세요.
0이나 음수가 있는 배열에서 윈도우를 재사용하는 경우입니다. 이 방법은 모든 값이 양수라는 조건에 의존합니다. 이 문제에서는 이를 보장하지만, 변형 문제에서는 그렇지 않을 수 있습니다.

자주 묻는 질문4

Minimum Size Subarray Sum의 시간 복잡도는 얼마인가요?

슬라이딩 윈도우 풀이의 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다. 내부 반복문 때문에 시간 복잡도가 이차 시간이 될 것처럼 보이지만, left는 앞으로만 이동하므로 전체 실행 동안 최대 n번 이동합니다. 접두사 합 버전의 시간 복잡도는 O(n log n)이고, 모든 시작 위치를 확인하는 방법의 시간 복잡도는 O(n²)입니다.

슬라이딩 윈도우에는 왜 양수가 필요할까요?

윈도우를 줄이면 합이 작아지고 늘리면 커져야 합니다. 그렇지 않으면 왼쪽 요소를 제거할 때 답의 시작 부분을 버릴 수 있습니다. 음수가 있으면 이러한 순서가 깨집니다. 일반적인 해결 방법은 후보 시작점의 단조 덱과 함께 누적 합을 사용하는 것이며, 이 방법도 O(n)으로 실행됩니다.

O(n) 풀이가 있는데 왜 O(n log n) 누적 합 풀이를 배울까요?

면접관은 O(n) 답변 다음에 이 방법을 자주 물어봅니다. 이는 양수 값의 또 다른 활용법을 보여 줍니다. 접두사 합이 정렬되어 있으므로 이진 검색을 통해 누적 합이 임계값을 처음 넘어서는 위치를 찾을 수 있습니다. 이 기법은 가중치에 비례해 무작위로 인덱스를 선택하는 문제와 같은 다른 문제에서도 다시 쓰입니다.

부분 배열의 합이 정확히 target과 같아야 하나요?

아니요. target 이상인 모든 합이 해당됩니다. target = 15일 때, 9, 3, 7로 이루어진 윈도우의 합은 19이고 길이는 여전히 3입니다. 정확히 같은 합이 필요하다면, 양수 값에 대해서는 윈도우가 여전히 작동합니다. 합이 목표값보다 클 동안 윈도우를 줄이고, 합이 같을 때만 길이를 기록하세요.

Python

def minSubArrayLen(target, nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값

Minimum Size Subarray Sum

함수

제약 조건

예제

힌트

풀이

모든 시작 지점에서 확장하기

누적 합과 이진 탐색

슬라이딩 윈도우

함정과 경계 사례

자주 묻는 질문4

비슷한 문제