Python으로 정렬된 리스트에서 모든 쌍의 절대 차이 합 구하기

문제 개요

정렬된 숫자 리스트 nums가 주어졌을 때, 리스트 안의 모든 숫자 쌍 사이의 절대 차이의 합을 구하는 문제입니다. 이때 (i, j)와 (j, i)는 서로 다른 쌍으로 간주합니다. 즉, 순서가 있는 쌍(ordered pair) 기준으로 계산하며, 결과가 매우 커질 수 있으므로 10⁹+7로 나눈 나머지를 반환해야 합니다.

예시

입력이 nums = [2, 4, 8]이라면 출력은 24입니다.

|2 - 4| + |2 - 8| + |4 - 2| + |4 - 8| + |8 - 2| + |8 - 4| = 24

접근 방법

모든 쌍을 일일이 비교하면 O(n²)의 시간이 걸리지만, 리스트가 정렬되어 있다는 특성을 활용하면 O(n) 만에 해결할 수 있습니다.

핵심 아이디어는 각 원소가 전체 합에 기여하는 횟수를 세는 것입니다. 인덱스 i에 있는 원소 nums[i]는 다음과 같이 등장합니다.

자신보다 왼쪽(더 작은 값)에 있는 i개의 원소와 짝을 이룰 때 → +nums[i]로 기여
자신보다 오른쪽(더 큰 값)에 있는 (n-1-i)개의 원소와 짝을 이룰 때 → -nums[i]로 기여

따라서 각 원소의 기여도는 nums[i] × i − nums[i] × (n−1−i)가 되며, 이 값을 모두 더한 뒤 2를 곱하면 순서 있는 쌍 기준의 최종 답을 얻을 수 있습니다.

알고리즘 단계

m = 10^9 + 7을 설정합니다.
total = 0으로 초기화합니다.
i를 0부터 n-1까지 반복하며 total += (i*nums[i] - (n-1-i)*nums[i]) % m을 누적합니다.
(2*total) % m을 반환합니다.

구현 예제

class Solution:
    def solve(self, nums):
        m = 10**9 + 7
        total = 0
        for i in range(len(nums)):
            total += (i*nums[i] - (len(nums) - 1 - i)*nums[i]) % m
        return (2*total) % m

ob = Solution()
nums = [2, 4, 8]
print(ob.solve(nums))

입력

[2, 4, 8]

출력

복잡도 분석

시간 복잡도: O(n) — 리스트를 한 번만 순회합니다.
공간 복잡도: O(1) — 추가 메모리 없이 상수 변수만 사용합니다.