0과 1로만 이루어진 배열 A가 주어졌다고 가정해 봅시다. 여기서 K-비트 반전(K-bit flip)이란 길이가 K인 연속된 부분 배열을 선택하여 그 안의 모든 비트를 한꺼번에 뒤집는(0↔1) 연산을 의미합니다.
우리가 구해야 할 것은 배열 전체에 0이 하나도 남지 않도록 만들기 위해 필요한 최소 반전 횟수입니다. 만약 어떤 방법으로도 목표를 달성할 수 없다면 -1을 반환해야 합니다.
문제 예시
입력이 [0,0,0,1,0,1,1,0]이고 K = 3일 때, 정답은 3입니다. 세 번의 연산 과정은 다음과 같습니다.
- 1차: 인덱스 0~2를 반전 →
[1,1,1,1,0,1,1,0] - 2차: 인덱스 4~6을 반전 →
[1,1,1,1,1,0,0,0] - 3차: 인덱스 5~7을 반전 →
[1,1,1,1,1,1,1,1]
접근 방법: 그리디 + 차분 배열
이 문제는 그리디(Greedy) 전략과 차분 배열(Difference Array) 기법을 결합하면 O(n) 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 왼쪽부터 순차적으로 탐색하면서, 현재 위치의 비트가 여전히 0이라면 반드시 이 위치에서 시작하는 K-비트 반전을 수행해야 합니다. 이보다 늦게 처리하면 길이 K의 창이 배열 끝을 넘어갈 수 있기 때문입니다.
- 각 위치에 현재 적용 중인(만료되지 않은) 반전의 총 개수를 추적하기 위해
moves배열을 사용합니다. (moves[i] % 2 + A[i]) % 2가 0이라는 것은 누적된 반전 횟수와 원래 비트를 합쳐도 해당 자리가 여전히 0이라는 뜻이므로, 이때 새로운 반전을 시작합니다.- 새 반전을 시작하면
moves[i]를 1 증가시켜 반전 효과를 기록하고, 반전 범위가 끝나는 지점인moves[i + K]에 -1을 표시합니다. 그리고 카운터를 1 증가시킵니다. - 마지막 구간(
i + K > n)에서는 더 이상 새로운 반전을 시작할 수 없습니다. 따라서 이 구간을 탐색하는 도중 비트가 0으로 판명되면 -1을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minKBitFlips(vector<int>& A, int K){
int n = A.size();
vector<int> moves(n);
int i;
int counter = 0;
for (i = 0; i + K <= n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) {
moves[i] += 1;
if (i + K < n)
moves[i + K] -= 1;
counter++;
}
}
for (; i < n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2))
return -1;
}
return counter;
}
};
main(){
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << (ob.minKBitFlips(v, 3));
}입력
{0,0,0,1,0,1,1,0}, 3출력
3