문제 소개
n개의 원소를 가진 배열과 양의 정수 s가 주어졌다고 가정해 봅시다. 우리가 찾아야 할 것은 합이 s 이상이 되는 연속된 부분 배열 중 가장 짧은 길이입니다. 만약 조건을 만족하는 부분 배열이 하나도 존재하지 않는다면 0을 반환하면 됩니다.
예를 들어 배열이 [2,3,1,2,4,3]이고 s가 7이라면 정답은 2입니다. [4,3]이라는 부분 배열의 합이 정확히 7이 되면서, 조건을 만족하는 부분 배열 중 길이가 가장 짧기 때문입니다.
해결 전략: 슬라이딩 윈도우
이 문제는 두 개의 포인터를 활용한 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 오른쪽 끝을 확장하며 합을 늘리고, 조건을 만족하면 왼쪽 끝을 줄여가며 최소 길이를 탐색합니다.
구체적인 단계는 다음과 같습니다.
ans := 0, n := 배열 A의 크기, j := 0, sum := 0으로 초기화합니다.
i를 0부터 n-1까지 반복합니다.
sum := sum + A[i] — 현재 원소를 윈도우에 추가합니다.
sum - A[j] >= K이고 j <= i인 동안 다음을 반복합니다.
sum := sum - A[j] — 왼쪽 끝 원소를 윈도우에서 제거합니다.
j를 1 증가시킵니다.
만약 sum >= K라면,
ans가 0이거나 ans > (i - j + 1)일 때 ans := (i - j + 1)로 갱신합니다.
모든 반복이 끝나면 ans를 반환합니다.
이 방식은 각 원소가 최대 두 번(윈도우에 추가될 때 한 번, 제거될 때 한 번)만 처리되므로 시간 복잡도는 O(n)이며, 별도의 추가 공간 없이 동작하므로 공간 복잡도는 O(1)입니다.
C++ 구현 예제
다음 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSubArrayLen(int K, vector<int>& A) {
int ans = 0;
int n = A.size();
int j = 0;
int sum = 0;
for(int i = 0; i < n; i++){
sum += A[i];
while(sum - A[j] >= K && j <= i){
sum -= A[j];
j++;
}
if(sum >= K){
if(ans == 0 || ans > (i - j + 1)) ans = (i - j + 1);
}
}
return ans;
}
};
main(){
vector<int> v = {2,3,1,2,4,3};
Solution ob;
cout << ((ob.minSubArrayLen(7,v)));
}
입력
7 [2,3,1,2,4,3]
출력
2
마무리
슬라이딩 윈도우 기법은 배열에서 연속 구간의 합을 다루는 문제에 매우 유용한 패턴입니다. 특히 모든 원소가 양수인 경우에는 윈도우를 확장할 때 합이 증가하고 축소할 때 감소하므로, 이 기법을 안전하게 적용할 수 있습니다. 유사한 유형의 문제를 만났을 때 이 패턴을 활용해 보시기 바랍니다.