릿코드 1685. Sum of Absolute Differences in a Sorted Array 코틀린

문제:현재 i를 나머지 모든값에서 뺀 절대값의 합으로 만들어라

절대값이라 걍 곱해서 다더한거랑 뺄순없고
10^5니까 n^2도 안될듯
그럼 그냥 해시맵에 뺀 결과를 그대로 넣어두고 반복문밖에서 각각 더하기?

어짜피 정렬쳐도되니까 정렬을 치고 자기인덱스보다 작은거끼리 곱해서 다더한거랑 빼고,큰거끼리 다더해서 곱한거랑 빼서 더하기

 

실패

class Solution {
    fun getSumAbsoluteDifferences(nums: IntArray): IntArray {
        val numList = nums.toList().sorted()
        val resList= mutableListOf<Int>()
        val sumHashMap = hashMapOf<Int, Int>()
        for ((index,value) in numList.withIndex()){
            sumHashMap[index]=value
        }
        var count=0
        for ((index,value) in sumHashMap){
            count+=value
            sumHashMap[index]=count
        }
        println(sumHashMap)

        for ((index,value) in numList.withIndex()){


            val leftValue=((value * (index+1)) - (sumHashMap[index]?: 0) )
            val rightValue=((sumHashMap[numList.lastIndex]?: 0)-
                (sumHashMap[index]?: 0) - (value * (numList.size-(index+1))))
            val resValue = leftValue + rightValue
            resList.add(resValue)

        }

        println(resList)
        return resList.toIntArray()
    }
}

 

정답

class Solution {
    fun getSumAbsoluteDifferences(nums: IntArray): IntArray {
        val prefixSum = nums.scan(0) { sum, item -> sum + item }
        return IntArray(nums.size) { i ->
            i * nums[i] - prefixSum[i] + 
            prefixSum[prefixSum.size - 1] - prefixSum[i + 1] - (nums.size - 1 - i) * nums[i]
        }
    }
}

접근자체는 똑같았는데 구현에서 뭐하나 실수한듯