JavaScript 배열에서 특수한 쌍 찾기: 펜윅 트리(BIT)로 O(n log n)에 해결하기

문제 정의

정수 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 다음 두 조건을 모두 만족하는 인덱스 쌍 (i, j)의 개수를 세어 반환해야 합니다.

i < j (i가 j보다 앞선 인덱스)
arr[i] > 2 × arr[j] (앞쪽 요소가 뒤쪽 요소의 2배보다 큰 경우)

입력 및 출력 예시

함수의 입력이 다음과 같다면,

const input = [2, 4, 3, 5, 1];

출력은 다음과 같아야 합니다.

const output = 3;

출력 설명

조건을 만족하는 세 개의 쌍은 다음과 같습니다.

[4, 1], [3, 1], [5, 1]

값 4, 3, 5는 각각 마지막 요소인 1보다 두 배 이상 크고, 인덱스 순서 조건(i < j)도 함께 충족하기 때문입니다.

구현 코드

const arr = [2, 4, 3, 5, 1];
const peculiarPairs = (arr = []) => {
    let count = 0;
    let copy = arr.slice().sort((a,b)=> a - b);
    let bit = new Array(arr.length+1).fill(0);
    for (const num of arr){
        count += search(bit, indexed(copy, 2*num+1));
        bit = insert(bit, indexed(copy, num));
    };
    return count;
};
const search = (bit, i) => {
    let sum = 0;
    while (i < bit.length){
        sum += bit[i];
        i += i & -i;
    }
    return sum;
}
const insert = (bit, i) => {
    while (i > 0){
        bit[i] += 1;
        i -= i & -i;
    }
    return bit;
}
const indexed = (arr, val) => {
    let l = 0, r = arr.length-1, m = 0;
    while (l <= r) {
        m = l + ((r-l) >> 1);
        if (arr[m] >= val){
            r = m-1;
        }else{
            l = m+1;
        }
    }
    return l+1;
}
console.log(peculiarPairs(arr));

코드 설명: 바이너리 인덱스드 트리(BIT)

위 코드는 바이너리 인덱스드 트리(Binary Indexed Tree, BIT), 흔히 펜윅 트리(Fenwick Tree)라고 불리는 자료구조를 활용합니다.

BIT는 배열 형태로 표현되며, 각 노드는 입력 배열의 일부 구간 합을 저장합니다. 트리의 크기는 입력 배열의 크기와 같으며, 이 자료구조를 사용하면 접두사 합(prefix sum) 조회와 갱신을 O(log n) 시간에 처리할 수 있습니다.

각 함수의 역할을 정리하면 다음과 같습니다.

indexed(): 이진 탐색으로 특정 값이 정렬된 복사본 배열에서 차지할 인덱스를 찾습니다.
search(): BIT에서 해당 인덱스 이상의 값, 즉 2×num+1보다 크거나 같은 값이 지금까지 몇 번 등장했는지 누적합을 조회합니다.
insert(): 현재 숫자를 BIT에 기록하여 이후 등장하는 요소들과 비교할 수 있도록 준비합니다.

배열을 한 번만 순회하면서 각 요소마다 로그 시간 연산을 수행하므로 전체 시간 복잡도는 O(n log n)입니다. 모든 쌍을 이중 반복문으로 검사하는 O(n²) 방식보다 훨씬 효율적입니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.