구간 합(Range Sum)이란?
구간 합 rangeSum(i, j)은 배열에서 인덱스 i부터 j까지(i ≤ j)에 해당하는 요소들의 합으로 정의됩니다. 즉, 연속된 부분 배열의 요소들을 모두 더한 값이라고 할 수 있습니다.
문제 설명
이번 문제에서는 정수 배열 arr을 첫 번째 인자로, 두 개의 숫자 lower와 upper를 각각 두 번째, 세 번째 인자로 받는 JavaScript 함수를 작성해야 합니다.
함수는 가능한 모든 구간 합 중에서 [lower, upper] 범위(양 끝값 포함)에 속하는 구간 합의 개수를 반환해야 합니다.
예를 들어, 함수에 다음과 같은 입력값이 주어졌다고 가정해 보겠습니다.
const arr = [1, 4, 3]; const upper = 5; const lower = 2;
배열 [1, 4, 3]에서 만들 수 있는 연속 구간의 합은 1, 4, 3, 5(1+4), 7(4+3), 8(1+4+3)입니다. 이 중 [2, 5] 범위에 속하는 값은 3, 4, 5로 총 3개이므로, 출력 결과는 다음과 같아야 합니다.
const output = 3;
해결 코드
이 문제는 누적합(prefix sum)과 이진 탐색(binary search)을 조합하면 효율적으로 해결할 수 있습니다. 코드는 다음과 같습니다.
const arr = [1, 4, 3];
const upper = 5;
const lower = 2;
const countRangeSum = (arr = [], lower, upper) => {
const sums = [0];
let res = 0;
let last = 0;
let firstge = value => {
let l = 0, r = sums.length, m;
do {
m = Math.floor((r + l) / 2);
sums[m] < value ? l = m : r = m;
} while (r >= l + 2);
while (r > 0 && sums[r - 1] >= value ) {
r -= 1;
}
return r;
};
arr.forEach(num => {
last += num;
res += firstge(last - lower + 1) - firstge(last - upper);
sums.splice(firstge(last), 0, last);
});
return res;
};
console.log(countRangeSum(arr, lower, upper));
동작 원리
이 알고리즘의 핵심 아이디어는 다음과 같습니다.
1. 누적합 활용: 배열을 순회하면서 현재 위치까지의 누적합(last)을 계산합니다. 어떤 구간 [i, j]의 합은 'j까지의 누적합 − i−1까지의 누적합'과 같으므로, 두 누적합의 차이가 [lower, upper] 사이에 있는 경우를 찾으면 됩니다.
2. 정렬된 목록 유지: 배열 sums에는 지금까지 등장한 누적합들이 항상 오름차순으로 정렬된 상태로 저장됩니다. 초기값으로 0을 넣어두는 이유는 인덱스 0부터 시작하는 구간도 고려하기 위해서입니다.
3. 이진 탐색으로 개수 세기: 내부 함수 firstge는 이진 탐색을 통해 특정 값 이상인 요소가 처음 나타나는 위치를 찾습니다. firstge(last - lower + 1)은 lower 이하인 누적합의 개수를, firstge(last - upper)는 upper 미만인 누적합의 개수를 의미하므로, 두 값의 차이가 곧 현재 시점에서 유효한 구간 합의 개수가 됩니다.
4. 삽입 정렬 방식 추가: 마지막으로 splice를 사용해 현재 누적합을 올바른 위치에 삽입하여 정렬 상태를 유지합니다.
이 접근 방식은 탐색 자체는 O(log n)으로 빠르지만, 배열 삽입에 O(n)이 걸릴 수 있어 최악의 경우 전체 O(n²)의 시간 복잡도를 가집니다. 그럼에도 불구하고 단순한 브루트포스(O(n²) 구간 전체 검사)보다 실제 동작이 훨씬 빠르고, 메모리 사용량도 적습니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
3
[2, 5] 범위에 속하는 구간 합이 정확히 3개임을 확인할 수 있습니다.