1685. Sum of Absolute Differences in a Sorted Array

[zeikar]

Problem link

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array

Problem Summary

배열이 주어질 때 각 원소와 다른 원소와의 차이의 절대값의 합을 모두 구하는 문제.

Solution

문제를 잘 노려보니 뭔가 규칙이 보일 듯 하다.
일단 모든 원소를 다 더해보면 뭔가 나오는데 첫 번째 답은 모든 원소의 합 - 자기 자신 * 배열 길이가 된다. 크기 순으로 정렬이 되어 있으므로

|a1 - a2| + |a1 - a3| ... |a1 - an| = |a2 - a1| + |a3 - a1| ... |an - a1| = a1 + a2 + a3 ... an - (a1 * n)

여기부터 시작해보자.

두 번째 원소는 첫 번째 원소보다 큰 만큼 절대값의 합이 작아지게 되고 반대로 첫 번째보다 절대값이 커진다.... 말로 하니 쉽지 않은데

s2 = s1 - (a2 - a1) * (n - 1) + (a2 - a1) * 1

이런 느낌이 되고 일반화를 하면

si = sj - (ai - aj) * (n - i) + (ai - aj) * i (j=i-1)

직접 절대값이 어떤 식으로 변하는지 직관적?으로 보면 답이 나오는 문제였다.

증명은 다른 사람이 포스트로 이미 써놓은 것이 있으니 참고 바람.
https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/solutions/4329011/concise-100-approach-and-mathematical-proof/

Example

예시 2번을 보자.

nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

인데 전체 합은 29 이고 첫 번째 정답은 29 - 1*5 = 24 이다.
두 번째는 24 - 3 * 4 + 3 = 15가 된다.
비슷하게 15 - 2 * 3 + 2 = 13 이며
15 = 13 - 2 * 2 + 2 * 3
21 = 15 - 2 * 1 + 2 * 4 가 된다.

Source Code

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        n = len(nums)
        s = sum(nums)
        res = [s - nums[0] * n]
        for i in range(1, n):
            diff = nums[i] - nums[i - 1]
            res.append(res[-1] - diff * (n - i) + diff * i)
        return res