자바스크립트로 0과 1 개수가 같은 최장 연속 부분 배열 구하기

문제 소개

0 또는 1만으로 이루어진 이진 배열(binary array) arr를 입력받아, 배열 안에서 0과 1의 개수가 동일하게 포함된 연속 부분 배열(contiguous subarray) 중 가장 긴 것의 길이를 반환하는 자바스크립트 함수를 작성해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

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

이 경우 기대하는 출력 결과는 다음과 같습니다.

const output = 6;

출력 설명

배열의 첫 6개 요소는 1, 0, 0, 1, 0, 1입니다. 여기에는 1이 세 개, 0이 세 개로 서로 개수가 같으므로, 조건을 만족하는 가장 긴 연속 부분 배열의 길이는 6이 됩니다.

예제 코드

이 문제를 해결하는 코드는 다음과 같습니다.

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

const findMaxLength = (arr = []) => {
    const { length } = arr;
    if (length < 2) {
        return 0;
    }
    const map = new Map();
    map.set(0, -1);
    let sum = 0;
    let max = 0;
    for (var i = 0; i < length; i++) {
        sum += arr[i] === 0 ? -1 : 1;
        if (map.has(sum)) {
            max = Math.max(max, i - map.get(sum));
        } else {
            map.set(sum, i);
        }
    }
    return max;
};

console.log(findMaxLength(arr));

코드 설명

이 알고리즘의 핵심 아이디어는 누적합(prefix sum) 기법을 활용하는 것입니다.

배열을 순회하면서 0은 -1로, 1은 +1로 취급하여 누적합을 계산합니다.
특정 구간의 합이 0이 된다는 것은, 그 구간 안에 0과 1의 개수가 정확히 절반씩 포함되어 있다는 의미입니다.
Map 객체에는 각 누적합 값이 처음 등장한 인덱스를 저장합니다. 이후 동일한 누적합이 다시 나타나면, 두 인덱스 사이 구간의 합은 반드시 0이므로 그 거리가 조건을 만족하는 부분 배열의 길이가 됩니다.
map.set(0, -1) 초기화는 배열의 시작 지점(인덱스 0 이전)부터 특정 인덱스까지의 구간도 올바르게 계산하기 위해 필요합니다.

이 방식은 각 요소를 한 번만 순회하므로 시간 복잡도 O(n), Map 저장 공간만큼 공간 복잡도 O(n)으로 문제를 매우 효율적으로 해결할 수 있습니다.

실행 결과

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