JavaScript로 최대 한 개의 0을 뒤집어 만들 수 있는 연속된 1의 최대 길이 구하기

문제

0과 1로만 구성된 이진 배열 arr를 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 우리 함수는 배열에서 최대 한 개의 0을 1로 뒤집을 수 있다고 가정할 때, 만들 수 있는 연속된 1의 최대 개수를 반환해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어지면 −

const arr = [1, 0, 1, 1, 0];

출력은 다음과 같아야 합니다 −

const output = 4;

출력 설명

배열에서 인덱스 1에 있는 0을 1로 뒤집으면 [1, 1, 1, 1, 0]이 되어 앞부분에 연속된 네 개의 1을 얻을 수 있기 때문입니다.

풀이 접근 방식: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(투 포인터) 기법으로 효율적으로 해결할 수 있습니다. 윈도우 안에 0이 최대 한 개만 존재하도록 범위를 조정해가며, 각 순간의 윈도우 길이 중 최댓값을 기록하는 방식입니다.

예제 코드

이를 구현한 코드는 다음과 같습니다 −

const arr = [1, 0, 1, 1, 0];
const findMaximumOne = (nums = []) => {
   let count = 0;
   let first = -1;
   let i = 0, j = 0;
   let res = -Infinity;
   while(j < nums.length){
      if(nums[j] === 1){
         res = Math.max(res, j-i+1);
      }else{
         count++;
         if(count === 2){
            i = first + 1;
            count--;
         };
         first = j;
      };
      j++;
   };
   return res;
};
console.log(findMaximumOne(arr));

코드 설명

i와 j: 현재 탐색 범위(윈도우)의 시작점과 끝점을 나타내는 두 포인터입니다.
count: 윈도우 내에서 만난 0의 개수를 추적합니다.
first: 가장 최근에 만난 0의 인덱스를 기억합니다.
0을 두 번째로 만나는 순간, 윈도우의 시작점 i를 첫 번째 0 바로 다음 위치로 옮기고 count를 감소시켜, 윈도우 안에는 항상 0이 한 개 이하만 존재하도록 유지합니다.
배열 요소를 순회할 때마다 res에 현재 윈도우 길이(j - i + 1)의 최댓값을 저장합니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.

출력

콘솔에 출력되는 결과는 다음과 같습니다 −