문제 개요
0과 1로만 구성된 크기 N의 배열이 주어졌을 때, 단 하나의 0을 1로 바꿔서 가장 긴 연속된 1의 시퀀스를 얻으려면 어느 위치의 0을 바꿔야 할까요?
예를 들어 배열이 arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]이라고 가정해 봅시다. 이 경우 정답은 인덱스 9입니다. 인덱스 9의 0을 1로 바꾸면 앞쪽의 세 개(인덱스 6~8)와 뒤쪽의 세 개(인덱스 10~12)가 하나로 연결되어 총 7개로 이루어진 최대 연속 1 시퀀스가 만들어지기 때문입니다.
알고리즘 접근 방식
이 문제는 세 개의 인덱스를 추적하는 방식으로 배열을 딱 한 번(O(N)) 순회하며 해결할 수 있습니다.
- curr: 현재 탐색 중인 인덱스
- pz (previous zero): 직전에 등장한 0의 인덱스
- ppz (previous to previous zero): 그 이전에 등장한 0의 인덱스
배열을 순회하면서 현재 원소가 0일 때마다 curr과 ppz의 차이를 계산합니다. 이 차이는 두 0 사이에 있는 연속된 1의 구간 길이(교체 대상인 0 포함)를 의미합니다. 계산된 값이 지금까지의 최댓값(count_max)보다 크면 최댓값과 해당 위치(index)를 갱신한 뒤, ppz와 pz 값을 업데이트하고 다음으로 진행합니다.
순회가 모두 끝난 후에는 마지막 0부터 배열 끝까지의 구간도 확인해야 합니다. n - ppz가 count_max보다 크다면 index를 pz로 갱신합니다. 최종적으로 반환되는 index가 바로 1로 교체했을 때 가장 긴 연속 1 시퀀스를 얻을 수 있는 0의 위치입니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
int count_max = 0;
int index;
int pz = -1;
int ppz = -1;
for (int curr = 0; curr<n; curr++) {
if (arr[curr] == 0) {
if (curr - ppz > count_max) {
count_max = curr - ppz;
index = pz;
}
ppz = pz;
pz = curr;
}
}
if (n - ppz > count_max)
index = pz;
return index;
}
int main() {
bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "교체할 0의 인덱스는 " << findIndex(arr, n);
}실행 결과
교체할 0의 인덱스는 9
복잡도 분석
이 알고리즘은 배열 전체를 한 번만 순회하므로 시간 복잡도는 O(N)이며, 세 개의 인덱스 변수 외에 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.