C++로 이진 배열에서 가장 긴 연속된 1의 시퀀스를 만들기 위해 0을 1로 바꿀 인덱스 찾기 (Set-2)

핵심 개념

0과 1로 구성된 배열이 주어졌을 때, 하나의 0을 1로 바꿔서 가장 긴 연속된 1의 시퀀스를 얻으려면 어떤 위치의 0을 바꿔야 할까요? 이 문제는 시간 복잡도 O(n), 보조 공간 복잡도 O(1) 조건으로 해결해야 합니다.

입력 및 출력 예시

입력:

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

출력:

인덱스 10

배열 인덱스가 0부터 시작한다고 가정하면, 인덱스 10의 0을 1로 바꿨을 때 가장 긴 연속된 1의 시퀀스가 만들어집니다.

또 다른 예시를 살펴보겠습니다.

입력:

arr[] = {1, 1, 1, 1, 1, 0}

출력:

인덱스 5

해결 방법: 0을 기준으로 좌우의 1 개수 세기

이 방법의 핵심 아이디어는 각 0을 기준으로 왼쪽과 오른쪽에 있는 1의 개수를 세는 것입니다. 주변에 가장 많은 1을 가진 0의 인덱스가 곧 우리가 찾아야 하는 인덱스가 됩니다.

이를 위해 다음과 같은 변수들을 사용합니다.

leftCnt — 현재 살펴보고 있는 0의 왼쪽에 있는 1의 개수를 저장합니다.
rightCnt — 현재 살펴보고 있는 0의 오른쪽에 있는 1의 개수를 저장합니다.
maxIndex — 주변에 가장 많은 1을 가진 0의 인덱스를 저장합니다.
lastInd — 마지막으로 발견한 0의 인덱스를 저장합니다.
maxCnt — maxIndex 위치의 0을 1로 바꿨을 때 얻을 수 있는 1의 개수를 저장합니다.

알고리즘 진행 과정

배열을 순회하면서 현재 요소가 1이면 rightCnt를 계속 증가시킵니다. 다음 0이 인덱스 i에 있다고 가정합니다.
현재 발견한 0이 첫 번째 0인지 확인합니다. lastInd에 유효한 인덱스 값이 없다면(-1이라면) 첫 번째 0입니다.
첫 번째 0이라면 lastInd를 i로 갱신합니다. 이때 rightCnt 값은 이 0의 왼쪽에 있는 1의 개수가 됩니다.
leftCnt를 rightCnt 값으로 설정한 후, rightCnt를 다시 계산합니다. 현재 0이 첫 번째 0이 아니라면, lastInd 위치의 0 주변에 있는 1의 개수는 leftCnt + rightCnt가 됩니다.
leftCnt + rightCnt + 1 값이 현재 maxCnt보다 크다면, maxCnt를 leftCnt + rightCnt + 1로 갱신하고 maxIndex = lastInd로 설정합니다.
이후 인덱스 i의 0에 대해 rightCnt가 새로운 leftCnt가 되고, lastInd는 i가 됩니다. 다시 rightCnt를 계산하여 1의 개수를 maxCnt와 비교하고, 필요에 따라 maxCnt와 maxIndex를 갱신합니다.
배열의 모든 후속 0 요소에 대해 이 과정을 반복합니다.
lastInd에는 현재 leftCnt와 rightCnt가 계산되고 있는 0의 인덱스가 저장됩니다.
최종적으로 1로 바꿔야 하는 0의 인덱스가 maxIndex에 저장됩니다.

C++ 구현 예제

// 가장 긴 연속된 1의 시퀀스를 얻기 위해
// 1로 바꿀 0의 인덱스를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 가장 긴 연속된 1의 시퀀스를 얻기 위해
// 1로 바꿀 0의 인덱스를 반환하는 함수.
// 배열에 0이 없다면 -1을 반환합니다.
int maxOnesIndex(bool arr1[], int n1){
    int i = 0;
    // 현재 0 요소의 왼쪽에 있는 1의 개수 저장
    int leftCnt1 = 0;
    // 현재 0 요소의 오른쪽에 있는 1의 개수 저장
    int rightCnt1 = 0;
    // 주변에 가장 많은 1을 가진 0의 인덱스
    int maxIndex1 = -1;
    // 마지막으로 발견한 0 요소의 인덱스
    int lastInd1 = -1;
    // maxInd1 위치의 0을 1로 바꿨을 때의 1 개수
    int maxCnt1 = 0;
    while (i < n1) {
        // 현재 요소가 1인 동안 카운트 증가
        if (arr1[i]) {
            rightCnt1++;
        }
        else {
            // 현재 0 요소가 첫 번째 0이 아니라면,
            // lastInd 위치의 0을 교체했을 때 얻는
            // 1의 개수를 계산합니다.
            // 필요시 maxCnt와 maxIndex를 갱신합니다.
            if (lastInd1 != -1) {
                if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
                    maxCnt1 = leftCnt1 + rightCnt1 + 1;
                    maxIndex1 = lastInd1;
                }
            }
            lastInd1 = i;
            leftCnt1 = rightCnt1;
            rightCnt1 = 0;
        }
        i++;
    }
    // 마지막 0 요소를 1로 교체했을 때의
    // 연속된 1의 개수를 확인합니다.
    if (lastInd1 != -1) {
        if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
            maxCnt1 = leftCnt1 + rightCnt1 + 1;
            maxIndex1 = lastInd1;
        }
    }
    return maxIndex1;
}

// 드라이버 함수
int main(){
    bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
    // bool arr1[] = {1, 1, 1, 1, 1, 0};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << "교체할 0의 인덱스는 "
    << maxOnesIndex(arr1, n1);
    return 0;
}

실행 결과

교체할 0의 인덱스는 10

마무리

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 변수 몇 개만 사용하므로 보조 공간 복잡도는 O(1)입니다. 슬라이딩 윈도우 기법과 유사한 이 접근 방식은 각 0을 기준으로 좌우의 연속된 1의 개수를 효율적으로 추적하여 최적의 교체 위치를 찾아냅니다.