문제 이해하기
첫 번째 인수로 숫자 배열 arr를, 두 번째 인수로 숫자 num을 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 요소들의 합이 num으로 나누어 떨어지는 연속된(contiguous), 비어 있지 않은 부분 배열의 개수를 반환해야 합니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr = [4, 5, 0, -2, -3, 1]; const num = 5;
그렇다면 기대하는 출력 결과는 다음과 같습니다.
const output = 7;
출력 설명
합이 5로 나누어 떨어지는 부분 배열은 총 7개입니다.
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
예제 코드
이 문제를 해결하는 코드는 다음과 같습니다.
const arr = [4, 5, 0, -2, -3, 1];
const num = 5;
const divisibleSum = (arr = [], num = 1) => {
const map = {};
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
const key = ((sum % num) + num) % num;
map[key] = map[key]+1||1;
};
let s = 0;
for (let i = 0; i < num; i++) {
if (map[i] > 1) {
s += (map[i] * (map[i] - 1)) / 2;
}
}
return s + (map[0]||0);
};
console.log(divisibleSum(arr, num));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
7
코드 동작 원리
이 풀이의 핵심은 누적합(prefix sum)과 나머지 연산입니다. 모든 부분 배열을 일일이 확인하면 시간 복잡도가 O(n²)까지 늘어날 수 있지만, 누적합의 나머지를 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.
1단계: 누적합의 나머지 기록
배열을 순회하면서 각 위치까지의 누적합을 구하고, 이를 num으로 나눈 나머지를 키로 하는 객체(map)에 등장 횟수를 기록합니다. 여기서 ((sum % num) + num) % num 연산을 사용하는 이유는, 자바스크립트에서 음수에 대한 나머지 연산 결과가 음수가 될 수 있기 때문입니다. 이 식은 항상 0 이상 num 미만의 올바른 나머지를 보장합니다.
2단계: 같은 나머지끼리의 조합 계산
두 누적합을 num으로 나눈 나머지가 서로 같다면, 그 두 지점 사이 구간의 합은 반드시 num으로 나누어 떨어집니다. 따라서 어떤 나머지 값이 k번 등장했다면, 그중 두 지점을 고르는 조합 k × (k − 1) / 2개의 부분 배열이 조건을 만족합니다.
3단계: 처음부터 시작하는 구간 처리
마지막에 map[0]을 더하는 이유는, 배열의 첫 번째 요소부터 특정 위치까지의 누적합 자체가 이미 num으로 나누어 떨어지는 경우(나머지가 0인 경우)를 별도로 세어 주기 위함입니다.
이 알고리즘의 시간 복잡도는 O(n + num), 공간 복잡도는 O(num)으로, 중첩 반복문을 사용하는 완전 탐색 방식보다 훨씬 효율적입니다.