C++로 해결하는 Max Consecutive Ones II – 슬라이딩 윈도우 기법

문제 소개

이진 배열(0과 1로만 구성된 배열)이 주어졌을 때, 최대 한 번의 0을 1로 뒤집을 수 있다면 배열에서 만들 수 있는 최대 연속된 1의 개수를 구하는 문제입니다.

예를 들어 입력이 [1,0,1,1,0]이라면 출력은 4가 됩니다. 첫 번째 0을 뒤집으면 [1,1,1,1,0]이 되어 앞쪽에 연속된 1이 4개 생기기 때문입니다.

접근 방법: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 O(n) 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 두 개의 포인터(i, j)로 윈도우를 유지하며, 윈도우 내부의 0의 개수가 최대 1개를 넘지 않도록 관리합니다.
• 0의 개수가 2개 이상이 되면 왼쪽 포인터(j)를 이동시켜 0이 하나만 남을 때까지 윈도우를 축소합니다.
• 매 단계마다 현재 윈도우의 길이(i − j + 1)로 정답을 갱신합니다.

알고리즘 단계

1. ret = 1, n = nums.size()로 초기화합니다.
2. 배열이 비어 있다면(n == 0) 0을 반환합니다.
3. j = 0(왼쪽 포인터), zero = 0(윈도우 내 0의 개수)로 초기화합니다.
4. i를 0부터 n−1까지 순회하며 다음을 반복합니다.
   • nums[i] == 0이면 zero를 1 증가시킵니다.
   • j <= i이면서 zero > 1인 동안, nums[j] == 0이면 zero를 1 감소시키고 j를 증가시킵니다.
   • ret을 max(ret, i - j + 1)로 갱신합니다.
5. ret을 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
   int findMaxConsecutiveOnes(vector<int>& nums) {
      int ret = 1;
      int n = nums.size();
      if (!n)
         return 0;
      int j = 0;
      int zero = 0;
      for (int i = 0; i < n; i++) {
         if (nums[i] == 0) {
            zero++;
         }
         while (j <= i && zero > 1) {
            if (nums[j] == 0) {
               zero--;
            }
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};

int main(){
   Solution ob;
   vector<int> v = {1,0,1,1,1,0,1,1};
   cout << (ob.findMaxConsecutiveOnes(v));
   return 0;
}

실행 결과

입력

{1,0,1,1,1,0,1,1}

출력

6

동작 설명

입력 배열 {1,0,1,1,1,0,1,1}에서 인덱스 5의 0을 뒤집으면 {1,0,1,1,1,1,1,1}이 되어 인덱스 2부터 7까지 총 6개의 연속된 1을 얻을 수 있습니다. 이 값이 해당 배열에서 만들 수 있는 최대 연속 1의 개수입니다.

복잡도 분석

• 시간 복잡도: O(n) — 각 원소를 최대 두 번(윈도우 확장 및 축소) 방문합니다.
• 공간 복잡도: O(1) — 추가 자료구조 없이 상수 개의 변수만 사용합니다.