[LeetCode] 315. Count of Smaller Numbers After Self

😎풀이

1. 병합 정렬을 수행한다.
   1-1. 수행 시 우측 요소와 비교하여 현재 수 보다 작은 수를 카운트 한다.
   1-2. 병합 정렬된 결과를 반영한다.
2. 결과를 반환한다.

class NumberIndex {
    value: number
    index: number
    constructor(value: number, index: number) {
        this.value = value
        this.index = index
    }
}

function countSmaller(nums: number[]): number[] {
    const n = nums.length
    const result = Array(n).fill(0)
    const indices = nums.map((value, index) => new NumberIndex(value, index))
    function mergeSort(start: number, end: number) {
        if(end - start <= 1) return
        const mid = Math.floor((start + end) / 2)
        mergeSort(start, mid)
        mergeSort(mid, end)
        const merged = []
        let i = start
        let j = mid
        let rightCount = 0
        while(i < mid || j < end) {
            if(j === end || (i < mid && indices[i].value <= indices[j].value)) {
                result[indices[i].index] += rightCount
                merged.push(indices[i])
                i++
            } else {
                rightCount++
                merged.push(indices[j])
                j++
            }
        }
        for(let k = start; k < end; k++) {
            indices[k] = merged[k - start]
        }
    }
    mergeSort(0, n)
    return result
};