문제 소개
0과 1로만 이루어진 배열 A가 주어지고, 최대 K개의 값을 0에서 1로 바꿀 수 있다고 가정해 보겠습니다. 이때 1만으로 구성된 가장 긴 연속(contiguous) 부분 배열의 길이를 구하는 것이 목표입니다.
예를 들어 A = [1,1,1,0,0,0,1,1,1,1,0]이고 k = 2라면 정답은 6이 됩니다. 두 개의 0을 1로 뒤집으면 배열이 [1,1,1,0,0,1,1,1,1,1,1] 형태가 되어, 가장 긴 1의 연속 구간 길이가 6이기 때문입니다.
해결 접근 방식: 슬라이딩 윈도우(Sliding Window)
이 문제는 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 윈도우 안에 포함된 0의 개수가 K를 초과하지 않도록 왼쪽 경계(j)와 오른쪽 경계(i)를 조절하면서 윈도우의 최대 크기를 추적하는 방식입니다.
구체적인 단계는 다음과 같습니다.
ans := 0,j := 0,n := 배열의 크기로 초기화합니다.- i를 0부터 n−1까지 순회합니다.
- A[i]가 0이면 k를 1 감소시킵니다.
- j ≤ i 이고 k < 0인 동안 다음을 반복합니다.
- A[j]가 0이면 k를 1 증가시킵니다.
- j를 1 증가시켜 윈도우의 왼쪽 끝을 오른쪽으로 이동시킵니다.
- ans := max(i − j + 1, ans)로 갱신합니다.
- ans를 반환합니다.
여기서 k가 음수가 된다는 것은 윈도우 내부의 0 개수가 허용치 K를 초과했다는 의미입니다. 따라서 왼쪽 끝을 밀어내며 0을 하나 제거할 때까지 윈도우를 축소한 뒤, 현재 윈도우의 길이(i − j + 1)로 정답을 갱신합니다.
C++ 구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestOnes(vector<int>& A, int k) {
int ans = 0;
int j = 0;
int n = A.size();
for(int i = 0; i < n; i++){
if(A[i] == 0) k--;
while(j <= i && k <0){
if(A[j] == 0){
k++;
}
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {1,1,1,0,0,0,1,1,1,1,0};
Solution ob;
cout <<(ob.longestOnes(v, 3));
}
입력
[1,1,1,0,0,0,1,1,1,1,0] 3
출력
10
k = 3인 경우에는 세 개의 0을 모두 뒤집을 수 있으므로, 배열에서 마지막 0 하나만 남기고 나머지 구간을 이어 붙여 길이 10의 연속된 1 구간을 만들 수 있습니다.
복잡도 분석
배열의 각 원소는 i와 j 두 포인터에 의해 최대 한 번씩만 방문되므로, 시간 복잡도는 O(n)입니다. 또한 추가적인 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.