JavaScript 슬라이딩 윈도우 중앙값 구하기 — 이진 탐색으로 효율적으로 풀기

중앙값(Median)이란?

중앙값은 수학에서 정렬된(오름차순으로 정렬된) 숫자 목록의 가운데 값을 의미합니다.

만약 목록의 크기가 짝수라면 정확한 가운데 값이 존재하지 않습니다. 이 경우 중앙값은 가운데 두 값의 평균으로 정의됩니다.

문제 정의

정수 배열 arr를 첫 번째 인자로, 숫자 num(num <= arr.length)을 두 번째 인자로 받는 JavaScript 함수를 작성해야 합니다.

배열 arr에서 크기가 num인 각각의 윈도우(window)에 대해 중앙값을 계산하고, 그 결과를 새로운 배열에 차례대로 담아 마지막에 반환하면 됩니다.

예를 들어 함수의 입력이 다음과 같다면:

const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8];
const num = 3;

출력 결과는 다음과 같아야 합니다:

const output = [5, 5, 5, 3, 3, 8, 8, 4, 4, 6];

출력 과정 상세 설명

윈도우가 한 칸씩 이동할 때마다 해당 구간을 정렬한 뒤 중앙값을 구하는 과정은 아래 표와 같습니다.

구현 예제 코드

위 문제를 해결하는 코드는 다음과 같습니다.

const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8];
const num = 3;

// 이진 탐색: target이 삽입되거나 제거될 위치를 찾음
const binarySearch = (arr, target, l, r) => {
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (arr[mid] < target) l = mid + 1;
        else if (arr[mid] > target) r = mid;
        else return mid;
    };
    if (l === r) return arr[l] >= target ? l : l + 1;
}

const medianSlidingWindow = (arr = [], num = 1) => {
    let l = 0, r = num - 1, res = [];
    // 초기 윈도우를 정렬된 상태로 준비
    const window = arr.slice(l, num);
    window.sort((a, b) => a - b);
    while (r < arr.length) {
        // 윈도우 크기가 홀수면 가운데 값, 짝수면 두 값의 평균
        const median = num % 2 === 0 ?
        (window[Math.floor(num / 2) - 1] + window[Math.floor(num / 2)]) / 2 :
        window[Math.floor(num / 2)];
        res.push(median);
        // 왼쪽 끝 요소 제거
        let char = arr[l++];
        let index = binarySearch(window, char, 0, window.length - 1);
        window.splice(index, 1);
        // 오른쪽에 새 요소 삽입
        char = arr[++r];
        index = binarySearch(window, char, 0, window.length - 1);
        window.splice(index, 0, char);
    }
    return res;
};
console.log(medianSlidingWindow(arr, num));

코드 동작 원리

이 솔루션의 핵심 아이디어는 다음과 같습니다.

• 슬라이딩 윈도우가 오른쪽으로 한 칸 이동할 때마다, 왼쪽에서 빠지는 요소를 제거하고 오른쪽에서 들어오는 요소를 삽입합니다.
• 매번 전체 윈도우를 다시 정렬하는 대신, 이진 탐색(binary search)을 활용해 정렬된 상태를 유지하며 요소를 삽입·제거합니다.
• 이렇게 하면 매 단계마다 O(n log n)의 전체 정렬 비용 없이, O(log n)의 위치 탐색 비용만으로 윈도우를 관리할 수 있어 성능이 크게 향상됩니다.

실행 결과

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

[5, 5, 5, 3, 3, 8, 8, 4, 4, 6 ]