JavaScript로 합이 0인 부분 배열 존재 여부 확인하기

문제 개요

양수와 음수가 섞여 있는 숫자 배열을 입력받아, 원래 배열 안에 합이 0이 되는 연속된 부분 배열(subarray)이 존재하는지 판별하는 JavaScript 함수를 작성해야 합니다. 조건을 만족하면 true, 만족하지 않으면 false를 반환하면 됩니다.

접근 방식: 누적 합(Prefix Sum) 활용

핵심 아이디어는 간단합니다. 배열을 처음부터 끝까지 순회하면서 각 지점까지의 누적 합을 계산하고, 그 값을 Map 객체에 기록합니다. 순회 도중 다음 두 가지 상황 중 하나라도 발생하면 합이 0인 부분 배열이 반드시 존재합니다.

• 누적 합이 정확히 0이 되는 경우 → 배열 시작부터 현재 위치까지의 합이 0이라는 의미
• 누적 합이 이전에 이미 등장한 값과 동일한 경우 → 두 시점 사이 구간의 합이 0이라는 의미

Map을 사용하면 과거 누적 합을 O(1) 시간에 조회할 수 있으므로, 전체 알고리즘의 시간 복잡도와 공간 복잡도 모두 O(n)으로 매우 효율적입니다.

예제 코드

const arr = [4, 2, -1, 5, -2, -1, -2, -1, 4, -1, 5, -2, 3];
const zeroSum = arr => {
    const map = new Map();
    let sum = 0;
    for(let i = 0; i < arr.length; i++){
        sum += arr[i];
        if(sum === 0 || map.has(sum)){
            return true;
        }
        map.set(sum, i);
    };
    return false;
};
console.log(zeroSum(arr));

💡 팁: 흔히 보이는 map.get(sum) 대신 map.has(sum)을 사용하는 것이 더 안전합니다. 누적 합이 최초로 인덱스 0에서 기록된 경우 get()은 0(falsy 값)을 반환해 탐지에 실패할 수 있지만, has()는 값의 존재 여부만 정확하게 확인합니다.

실행 결과

true

결과 해설

예제 배열의 누적 합은 4 → 6 → 5 → 10 → 8 → 7 → 5 순으로 변합니다. 인덱스 2에서 누적 합이 5였는데, 인덱스 6에서 다시 5가 등장했습니다. 이는 인덱스 3~6 구간, 즉 [5, -2, -1, -2]의 합이 0이라는 뜻이며, 따라서 함수는 true를 반환합니다.