이 문제는 비교적 간단하지만, 간단하게 풀면 시간초과에 걸리기 때문에 조금은 생각을 해야 하는 문제입니다.
문제에서는 정렬된 정수 배열 nums가 주어집니다. 배열의 각 요소 'i' 에 대해, 해당 요소와 배열 내 다른 모든 요소 'j' 들과의 절대 차이인 |nums[i] - nums[j]| 의 합을 구하는 것이 목표입니다.
이 문제에서 각 원소를 순회하면서 절댓값 계산을 하면 nums의 길이가 10**5 까지 있기 때문에 시간초과가 날 수 밖에 없습니다.
이 문제를 효율적으로 해결하기 위해서는 누적합(prefix)와 역누적합(suffix)를 사용해야 합니다.
누적합(prefix sum)과 역누적합(suffix sum)의 사용은 꼭 알아야 하는 알고리즘 중에 하나입니다.
prefix sum에 대해 잠시 알아보고 가봅시다.
Prefix Sum
- Prefix sum은 배열의 일정 구간에 대한 합을 빠르게 계산하기 위해 사용하는 기법입니다. 이 방법은 주로 동적 프로그래밍이나 알고리즘 문제 해결에서 쓰이는데, 기본적인 아이디어는 배열의 각 인덱스에서 시작하여 그 지점까지의 합을 미리 계산해두는 것입니다.
- 예를 들어, 배열이 [3,1,4,5,9,2] 라면, prefix sum 배열은 [3,4,8,9,14,23,25] 가 됩니다. cumulative sum 알고리즘과 같은 누적합 알고리즘입니다. 이 알고리즘은 어떤 구간의 합을 구할 때, 빠르게 계산할 수 있습니다.
- 예를 들어, 원래 배열의 2번째부터 4번째 원소까지의 합을 구하고 싶다면, prefix sum 배열에서 4번째 원소의 값에서 1번째 원소의 값을 빼면 됩니다. (9-3 = 6)
- 이 기법은 특히 큰 데이터에서 많은 범위의 합을 자주 계산해야할 때 유용합니다.
※ Suffix Sum은 그 반대로 배열의 끝으로부터 처음 원소까지의 역누적합입니다.
그럼 이 알고리즘을 어떻게 이 문제에 활용할 수 있을까요?
접근 방식은 아래와 같습니다.
👉 오름차순 배열의 특성 이해하기 : 오름차순으로 정렬된 배열에서, 한 원소와 다른 모든 원소 간의 차이의 합은, 그 원소보다 작은 모든 원소의 합에서 해당 원소의 값에 그 원소의 인덱스를 곱한 값을 빼고, 해당 원소의 값에 (배열의 길이-그 원소의 인덱스 -1)을 곱한 값에서 그 원소보다 큰 모든 원소의 합을 빼는 방식으로 계산할 수가 있습니다.
...
...
아니 무슨 소리세요?
...
...
이건 예시를 들어서 제가 설명드리겠습니다.
먼저, 각 원소의 차이의 절댓값을 계산하는 로직을 짚고 넘어가봅시다.
위 설명을 토대로 [1,3,5,7,10] 이라는 오름차순으로 정렬된 배열이 있다고 가정해봅시다.
여기서 각 원소에 대한 왼쪽 원소들과의 차이와 오른쪽 원소들과의 차이를 계산하는 방법을 살펴볼 것입니다.
prefix sum과 suffix sum을 먼저 확인해보면,
prefixSum : [1, 4, 9, 16, 26]
suffixSum : [26, 25, 22, 17, 10]
이 됩니다.
이제, 배열의 각 원소에 대해 절댓값 차이를 계산하는 방법을 살펴봅시다.
1. 왼쪽 원소들과의 차이
원리: 배열의 i번째 원소를 기준으로 할 때, 이 원소는 왼쪽에 있는 모든 원소들보다 크거나 같습니다. 따라서, 이 원소와 왼쪽 원소들과의 차이는 다음과 같이 간단하게 계산할 수 있습니다.
계산 방법: i번째 원소와 왼쪽에 있는 모든 원소들과의 차이의 합 계산은
- 먼저, i번째 원소의 값을 i번 (왼쪽에 있는 원소의 수만큼) 더합니다.
- 그 다음, 이 결과에서 왼쪽에 있는 모든 원소들의 합을 빼면 됩니다. 이 합은 prefix sum 배열에서 i번째 원소의 직전 값, 즉 prefixSum[i - 1]로 구할 수 있습니다.
예를 들어, 5(세 번째 원소)의 경우:
- 왼쪽에 있는 원소들의 합은 '1 + 3 = 4' (prefixSum[1] 에서의 값) 이고,
- 5와 왼쪽 원소들과의 차이의 합은 '5 * 2 - 4 = 6' 입니다.
2. 오른쪽 원소들과의 차이
원리: 마찬가지로, i번째 원소는 오른쪽에 있는 모든 원소들보다 작거나 같습니다. 따라서, 이 원소와 오른쪽 원소들과의 차이도 간단히 계산할 수 있습니다.
계산 방법: i번째 원소와 오른쪽에 있는 모든 원소들과의 차이의 합 계산은
- 먼저, 오른쪽에 있는 모든 원소들의 합을 구하면, suffixSum 배열에서 i번째 값, 즉, suffixSum[i]로 구할 수 있습니다.
- 그 다음, 이 합에서 i 번째 원소의 값을 '(n - i - 1)' 번 (오른쪽에 있는 원소의 수만큼) 빼면 됩니다.
예를 들어, 5(세 번째 원소)의 경우:
- 오른쪽에 있는 원소들의 합은 '7 + 10 = 17' (suffixSum[3] 에서의 값) 이고,
- 5와 오른쪽 원소들과의 차이의 합은 '17 - 5 * 2 = 7' 입니다.
3. 최종합
각 원소에 대해 이 두 계산을 수행하고, 그 결과를 합하면 각 원소에 대한 절댓값 차이의 총합을 얻을 수 있습니다.
예를 들어, 5(세 번째 원소)의 경우:
- '6 + 7 = 13' 이 답이 된다.
위 예시에 대한 답은 [21,15,13,15,24] 가 나온다.
여기서 추가로 주의해야 할 점은 "경계값 처리" 인데, 배열의 첫 번째 요소와 마지막 요소의 절대 차이의 합은 별도로 계산합니다. 첫 번째 요소는 오른쪽 요소들만 고려하고, 마지막 요소는 왼쪽 요소들만 고려하면 됩니다.
아래는 최종 코드입니다.
class Solution(object):
def getSumAbsoluteDifferences(self, nums):
n = len(nums)
prefix = [0] * n
prefix[0] = nums[0]
for idx in range(1,n):
prefix[idx] = prefix[idx-1] + nums[idx]
# print(prefix)
suffix = [0] * n
suffix[-1] = nums[n-1]
for idx in range(n-2,-1,-1):
suffix[idx] = suffix[idx+1] + nums[idx]
# print(suffix)
answer = [0] * n
answer[0] = suffix[1] - nums[0] * (n-1)
answer[-1] = (n-1) * nums[-1] - prefix[-2]
for idx in range(1,n-1):
left = (nums[idx] * idx) - prefix[idx-1]
right = suffix[idx+1] - (nums[idx] * (n-idx-1))
answer[idx] = left + right
return answer
경계값 처리를 하기 위해 answer[0]과 answer[-1] 부분을 제외하고 for문을 돌렸습니다. 위 코드는 이해를 돕기 위해 코드를 길게 썼지만 아래처럼 더 간결하게 코드를 짤 수 있습니다.
class Solution(object):
def getSumAbsoluteDifferences(self, nums):
n = len(nums)
left = 0
right = sum(nums)
answer = []
for idx in range(n):
if len(answer) == 0:
answer.append(right-n*nums[idx])
else:
answer.append(nums[idx]*idx-left + right-nums[idx]-(n-idx-1)*nums[idx])
left += nums[idx]
right -= nums[idx]
return answer
prefix와 suffix 배열을 따로 만들지 말고 for문을 순회를 하면서 누적합계산과 역누적합 계산을 동시에 할 수 있습니다. 경계값 처리도 크게 신경쓸 필요가 없는 메모리 효율이 약간 더 좋은 코드입니다.
두 코드 모두
- 시간 복잡도: 시간 복잡도는 O(n)입니다. 각 요소에 대해 누적 합을 한 번만 계산하고, 절대 차이의 합도 한 번의 순회로 계산할 수 있기 때문입니다.
- 공간 복잡도: 공간 복잡도도 O(n)입니다. (입력 배열 nums와 answer가 O(n), 기타 변수들은 O(1))
이상으로 pefix sum, suffix sum, cumulative sum 과 관련한 1685. Sum of Absolute Differences in a Sorted Array 문제를 정리해봤습니다.