문제 정의
0 또는 1만 담고 있는 이진 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
배열 안의 0을 최대 num개까지만 1로 바꿀 수 있으며, 함수는 변경 작업을 마친 뒤 1로만 이루어진 가장 긴 연속(contiguous) 부분 배열의 길이를 반환해야 합니다.
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
const num = 2;
그렇다면 출력은 다음과 같아야 합니다.
const output = 6;
출력 설명
배열 뒤쪽에 있는 두 개의 0을 1로 바꾸면 마지막 6개 요소가 모두 1이 되기 때문입니다. 즉, 인덱스 5부터 10까지의 구간이 전부 1로 채워지면서 길이 6이 최댓값이 됩니다.
접근법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 O(n) 시간 복잡도 내에 효율적으로 해결할 수 있습니다.
동작 원리는 다음과 같습니다.
- 오른쪽 포인터(right)가 배열을 순회하며 0을 만날 때마다 남은 변경 가능 횟수(curr)를 하나씩 감소시킵니다.
- 변경 가능 횟수가 음수가 되면, 왼쪽 포인터(left)를 이동시켜 윈도우를 축소하고, 지나간 자리의 값이 0이었던 경우 변경 가능 횟수를 다시 회복시킵니다.
- 매 단계마다 현재 윈도우의 길이(right - left + 1)를 계산하여 최댓값을 갱신합니다.
각 요소가 최대 두 번만 방문되므로 전체 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.
예제 코드
위 접근법을 구현한 코드는 다음과 같습니다.
const arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
const num = 2;
const longestOnes = (arr = [], num = 1) => {
let max = 0;
let left = 0;
let curr = num;
for(let right = 0; right < arr.length; right++){
if(arr[right] === 0){
curr -= 1;
};
while(curr < 0){
if(arr[left] === 0){
curr += 1;
};
left += 1;
};
max = Math.max(max, right - left + 1);
};
return max;
};
console.log(longestOnes(arr, num));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
6