JavaScript로 합이 target과 같은 이진 부분 배열 개수 구하기

문제 정의

JavaScript 함수를 작성해야 합니다. 이 함수는 첫 번째 인자로 이진 배열(0과 1로만 이루어진 배열) arr을, 두 번째 인자로 숫자 target을 받습니다.

함수의 목표는 배열 arr 안에서 요소들의 합이 정확히 target과 일치하는 연속된 부분 배열(subarray)이 총 몇 개 존재하는지 세고, 그 개수를 반환하는 것입니다.

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

입력

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

출력

const output = 4;

출력 설명

조건을 만족하는 부분 배열은 다음 4개입니다.

[1,0,1]
[1,0,1,0]
[0,1,0,1]
[1,0,1]

접근 방법: 누적 합과 해시 맵 활용

모든 부분 배열을 하나씩 확인하는 브루트 포스 방식은 O(n²)의 시간 복잡도를 가지므로 비효율적입니다. 대신 누적 합(prefix sum)과 해시 맵을 조합하면 O(n) 시간에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• 배열을 순회하면서 현재 위치까지의 누적 합 sum을 유지합니다.
• 어떤 부분 배열의 합이 target이 되려면, 이전 어느 시점의 누적 합이 sum - target과 같아야 합니다.
• 따라서 각 누적 합 값이 몇 번 등장했는지 해시 맵에 기록하고, 매 단계마다 map[sum - target] 값을 더해주면 됩니다.

구현 코드

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

const countSubarrays = (arr = [], target = 1) => {
   const map = {}
   let sum = 0
   let count = 0
   for (const num of arr) {
      map[sum] = (map[sum] || 0) + 1
      sum += num
      count += map[sum - target] || 0
   }
   return count
};

console.log(countSubarrays(arr, target));

코드 동작 원리 상세 분석

위 코드가 어떻게 작동하는지 단계별로 살펴보겠습니다.

1. 순회 시작 전: 빈 부분 배열(합 0)을 고려하기 위해 루프 진입 직전에 현재 sum(초기값 0)을 먼저 맵에 기록합니다.
2. 누적 합 갱신: 각 요소를 더하면서 sum을 업데이트합니다.
3. 개수 카운트: sum - target이 과거에 등장한 적이 있다면, 그 등장 횟수만큼 새로운 유효한 부분 배열이 만들어진 것이므로 count에 더합니다.

예제 배열 [1, 0, 1, 0, 1]에서 누적 합은 1, 1, 2, 2, 3으로 변화하며, target = 2일 때 sum - 2인 지점들이 정확히 4번 발견되어 최종 결과 4가 반환됩니다.

결과

4

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 누적 합 값을 해시 맵에 저장해야 할 수 있습니다.

이 방식은 이진 배열뿐 아니라 음수를 포함한 일반 정수 배열에서도 동일하게 적용할 수 있는 범용적인 패턴이므로, 코딩 인터뷰에서 자주 활용되는 필수 기법 중 하나입니다.