문제

이진 배열 nums와 정수 k가 주어진다.
배열에 포함된 0을 최대 k개까지 1로 바꿀 수 있을 때, 연속된 1로 만들 수 있는 부분 배열의 최대 길이를 구하는 문제다.

• 문제 링크
• 난이도: Medium
• 핵심 알고리즘: Sliding Window

---

접근 방법

이 문제는 슬라이딩 윈도우로 해결할 수 있다.
연속된 구간 안에 포함된 0의 개수가 k개 이하라면, 해당 구간의 모든 숫자를 1로 만들 수 있다.
따라서 다음 조건을 만족하는 가장 긴 구간을 찾으면 된다.
구간 안에 포함된 0의 개수가 k개 이하인 가장 긴 부분 배열

윈도우의 양 끝을 가리키는 두 포인터를 사용한다.

• right: 윈도우의 오른쪽 경계를 확장한다.
• left: 조건을 만족하지 않을 때 왼쪽 경계를 줄인다.
• zeros: 현재 윈도우 안에 포함된 0의 개수를 관리한다.

---

동작 과정

1. right를 오른쪽으로 한 칸씩 이동하면서 현재 숫자가 0이면 zeros를 증가시킨다.

if (nums[right] === 0) {
  zeros++;
}

2. 만약 현재 윈도우 안의 0이 k개를 초과했다면, 더 이상 모든 0을 뒤집을 수 없다.
   이때 zeros <= k가 될 때까지 left를 이동시켜 윈도우를 축소한다.

while (zeros > k) {
  if (nums[left] === 0) {
    zeros--;
  }

  left++;
}

3. 조건을 다시 만족하게 되면 현재 윈도우의 길이를 계산하고 최댓값을 갱신한다.

maxLength = Math.max(maxLength, right - left + 1);

---

예시

nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
k = 2

윈도우 안에 0이 최대 2개까지 포함되도록 구간을 확장한다.

[0, 0, 1, 1, 1, 1]

이 구간의 0 두 개를 1로 바꾸면 다음과 같이 만들 수 있다.

[1, 1, 1, 1, 1, 1]

따라서 만들 수 있는 연속된 1의 최대 길이는 6이다.

---

코드

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
  let left = 0;
  let zeros = 0;
  let maxLength = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      zeros++;
    }

    // 0의 개수가 k를 초과하면
    // 조건을 만족할 때까지 윈도우의 왼쪽을 줄인다.
    while (zeros > k) {
      if (nums[left] === 0) {
        zeros--;
      }

      left++;
    }

    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
};

---

복잡도

시간 복잡도

O(n)

right 포인터는 배열을 한 번 순회하고, left 포인터 역시 최대 n번 이동한다.
중첩된 while문이 있지만 각 원소가 윈도우에 들어오고 나가는 횟수는 최대 한 번씩이므로 전체 시간 복잡도는 O(n)이다.

공간 복잡도

O(1)

입력 크기와 관계없이 몇 개의 변수만 사용한다.