JavaScript로 이진 배열에서 연속된 1의 최대 길이 구하기

이번 글에서는 0과 1만으로 구성된 이진 배열(binary array)을 유일한 인자로 받아, 배열 안에서 1이 연속으로 나타나는 가장 긴 구간의 길이를 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제 정의

예를 들어 입력 배열이 다음과 같다고 가정해 봅시다.

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

이 배열에서 1이 연속된 구간은 [1], [1, 1, 1], [1], [1, 1, 1, 1], [1]이며, 그중 가장 긴 구간은 마지막에서 두 번째에 위치한 길이 4의 구간입니다. 따라서 기대되는 출력값은 다음과 같습니다.

const output = 4;

접근 방법: 슬라이딩 윈도우(Sliding Window)

이 문제는 슬라이딩 윈도우 알고리즘을 사용하면 효율적으로 해결할 수 있습니다. 두 개의 포인터 left와 right를 활용하여 1로만 이루어진 가장 큰 윈도우(구간)를 추적하는 방식입니다.

• right 포인터가 배열을 순회하며 요소를 하나씩 확인합니다.
• 요소가 0이라면, 지금까지의 윈도우 크기(right - left)를 최댓값 max와 비교하여 갱신하고, 새로운 윈도우를 시작하기 위해 left를 right 다음 위치로 이동시킵니다.
• 요소가 1이라면 right만 앞으로 이동하며 윈도우를 확장합니다.

이 방식은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.

구현 코드

const arr = [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1];
const findMaxConsecutiveOnes = (arr = []) => {
    let left = 0;
    let right = 0;
    let max = 0;
    while (right < arr.length) {
        if (arr[right] === 0) {
            if (right - left > max) {
                max = right - left
            };
            right++;
            left = right;
        } else {
            right++
        };
    };
    return right - left > max ? right - left : max;
}
console.log(findMaxConsecutiveOnes(arr));

실행 결과

위 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.

4

정리

슬라이딩 윈도우 기법을 활용하면 이진 배열에서 연속된 1의 최대 길이를 선형 시간(O(n))에 효율적으로 구할 수 있습니다. 이 패턴은 '최대 연속 부분 배열', 'k개의 0을 뒤집어 얻을 수 있는 최대 연속 1' 등 다양한 변형 문제에도 그대로 응용할 수 있으니 꼭 익혀두시길 바랍니다.