배열 A가 주어졌을 때, 합이 K 이상이 되는 가장 짧은 비어 있지 않은 연속 부분 배열(subarray)의 길이를 구하는 문제입니다. 만약 조건을 만족하는 부분 배열이 존재하지 않는다면 -1을 반환해야 합니다.
예를 들어, 입력이 [5, 3, -2, 2, 1]이고 K = 6이라면 출력은 2가 됩니다. 앞의 두 원소를 더한 값(5 + 3 = 8)이 6 이상이기 때문입니다.
접근 방법: 누적 합과 단조 큐(Monotonic Deque)
배열에 음수가 포함되어 있기 때문에 단순한 슬라이딩 윈도우 기법으로는 해결할 수 없습니다. 대신 누적 합(prefix sum)과 단조 덱(deque)을 활용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 누적 합 A[i]를 계산합니다. 이때 A[i] - A[j] >= K이면 인덱스 j+1부터 i까지의 부분 배열 합이 K 이상임을 의미합니다.
- 덱에는 누적 합이 오름차순을 유지하도록 인덱스를 저장합니다. 새로 들어오는 누적 합이 덱 뒤쪽의 값보다 작거나 같으면, 뒤쪽 값을 제거합니다. 해당 인덱스는 이후 시작점으로 사용될 가능성이 없기 때문입니다.
- A[i]에서 덱 앞쪽 인덱스의 누적 합을 뺀 값이 K 이상이면, 그 길이로 정답을 갱신하고 앞쪽 요소를 제거합니다.
알고리즘 단계
- n := 배열 A의 크기로 설정합니다.
- ans := n + 1로 초기화합니다(정답을 찾지 못했음을 나타내는 값).
- 정수형 덱 dq를 하나 정의합니다.
- i를 0부터 n-1까지 반복하며 다음을 수행합니다.
- i > 0이면 A[i] := A[i] + A[i-1]로 누적 합을 갱신합니다.
- A[i] >= K이면 ans := min(ans, i + 1)로 정답을 갱신합니다.
- 덱이 비어 있지 않고 A[i] - A[dq.front()] >= K인 동안, ans := min(ans, i - dq.front())로 갱신하고 덱의 앞 요소를 제거합니다.
- 덱이 비어 있지 않고 A[i] <= A[dq.back()]인 동안, 덱의 뒤 요소를 제거합니다.
- i를 덱의 뒤에 삽입합니다.
- 반복이 끝나면 ans가 n + 1이면 -1을, 그렇지 않으면 ans를 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestSubarray(vector<int> &A, int K) {
int n = A.size();
int ans = n + 1;
int j = 0;
int sum = 0;
deque<int> dq;
for (int i = 0; i < n; i++) {
if (i > 0)
A[i] += A[i - 1];
if (A[i] >= K) {
ans = min(ans, i + 1);
}
while (!dq.empty() && A[i] - A[dq.front()] >= K) {
ans = min(ans, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && A[i] <= A[dq.back()])
dq.pop_back();
dq.push_back(i);
}
return ans == n + 1 ? -1 : ans;
}
};
main(){
Solution ob;
vector<int> v = {5,3,-2,2,1};
cout << (ob.shortestSubarray(v, 6));
}입력
{5,3,-2,2,1}, 6출력
2
시간 및 공간 복잡도 분석
각 인덱스는 덱에 최대 한 번 삽입되고 한 번 제거되므로 전체 시간 복잡도는 O(n)입니다. 덱에는 최대 n개의 인덱스가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 음수가 포함된 배열에서 최단 부분 배열을 찾아야 하는 상황에서 매우 효율적인 접근 방식입니다.