문제 개요
배열 arr와 정수 target이 주어졌을 때, 각각의 원소 합이 정확히 target이 되면서 서로 겹치지 않는 두 개의 부분 배열(연속된 하위 배열)을 찾아야 합니다. 조건을 만족하는 답이 여러 개라면, 두 부분 배열 길이의 합이 가장 작은 경우를 선택해야 하며 그 최솟값을 반환합니다. 만약 조건을 만족하는 부분 배열이 하나도 없다면 -1을 반환합니다.
예를 들어 입력이 arr = [5,2,6,3,2,5], target = 5라고 해 보겠습니다. 합이 5가 되는 부분 배열은 [5], [3,2], [5]로 세 가지가 있습니다. 이중 길이가 1인 두 부분 배열을 선택하면 길이의 합이 2로 최소가 되므로, 정답은 2입니다.
해결 전략
이 문제는 누적합(prefix sum)과 해시 맵을 함께 사용하면 배열을 한 번만 순회하면서 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- latest 맵: 특정 누적합 값이 마지막으로 등장한 인덱스를 저장합니다. 이를 통해 임의의 구간 합을 빠르게 확인할 수 있습니다.
- best 배열: 인덱스 i까지 살펴봤을 때, 합이 target인 부분 배열 길이의 최솟값을 저장합니다.
- 현재 위치에서 target 합을 가지는 부분 배열을 찾으면, 그 시작 경계 이전까지의 best 값을 결합해 '겹치지 않는' 두 부분 배열 길이의 최소 합을 갱신합니다.
알고리즘 단계
- ans를 매우 큰 값(사실상 무한대 역할)으로 초기화합니다.
- arr와 같은 크기의 best 배열을 만들어 모든 값을 큰 값으로 채웁니다.
- prefix를 0으로 초기화하고, latest 맵에는 {0: -1}을 저장합니다.
- arr의 각 인덱스 i와 값 x에 대해 다음을 반복합니다.
- prefix에 x를 더합니다.
- (prefix - target)이 latest에 존재하는지 확인합니다. 존재한다면 해당 인덱스를 ii라고 할 때, 구간 [ii+1, i]의 합이 정확히 target입니다.
- ii가 유효한 인덱스(0 이상)라면, ans를 ans와 (i - ii + best[ii]) 중 작은 값으로 갱신합니다. best[ii]는 ii 위치 이전에서 끝나는 부분 배열 중 최단 길이이므로, 두 부분 배열은 절대 겹치지 않습니다.
- best[i]에 현재 부분 배열의 길이 (i - ii)를 저장한 뒤, best[i-1]과 비교하여 지금까지의 최솟값을 유지합니다.
- latest[prefix]에 현재 인덱스 i를 기록합니다.
- 모든 순회가 끝나면 ans가 초기값보다 작을 경우 ans를, 그렇지 않으면 -1을 반환합니다.
구현 예제 (Python)
def solve(arr, target):
ans = 999999
best = [999999]*len(arr)
prefix = 0
latest = {0: -1}
for i, x in enumerate(arr):
prefix += x
if prefix - target in latest:
ii = latest[prefix - target]
if ii >= 0:
ans = min(ans, i - ii + best[ii])
best[i] = i - ii
if i: best[i] = min(best[i-1], best[i])
latest[prefix] = i
return ans if ans < 999999 else -1
arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target))
입력
[5,2,6,3,2,5], 5
출력
2
동작 과정 상세 분석
입력 arr = [5,2,6,3,2,5]에서 누적합은 5, 7, 13, 16, 18, 23 순으로 계산됩니다.
- i = 0일 때 prefix = 5이고, prefix - target = 0이 latest에 존재하지만 해당 값이 -1이므로 ans는 갱신되지 않습니다. 대신 best[0] = 1이 기록됩니다. 즉, 첫 번째 원소 [5] 자체가 합 5인 부분 배열입니다.
- i = 4일 때 prefix = 18이고, prefix - target = 13이 latest에서 인덱스 2로 발견됩니다. 따라서 구간 [3, 2](길이 2)가 합 5인 부분 배열이며, 앞선 best[2] = 1과 결합해 ans = 2 + 1 = 3이 됩니다.
- i = 5일 때 prefix = 23이고, prefix - target = 18이 인덱스 4로 발견됩니다. 마지막 원소 [5](길이 1)와 이전 최적 부분 배열(길이 1)을 결합해 ans = 1 + 1 = 2로 갱신되며, 이것이 최종 답이 됩니다.
복잡도 분석
배열을 한 번만 순회하며 각 단계의 해시 맵 조회와 갱신은 O(1)이므로, 전체 시간 복잡도는 O(n)입니다. best 배열과 latest 맵에 추가 공간을 사용하므로 공간 복잡도 역시 O(n)입니다. 완전 탐색으로 두 부분 배열의 모든 조합을 확인하는 O(n²) 이상의 방법에 비해 훨씬 효율적입니다.