문제 개요
숫자 리스트 nums가 주어졌을 때, 하나의 수열 '너비(width)'는 그 수열 안에서 최댓값과 최솟값의 차이로 정의합니다. 이때 nums로 만들 수 있는 모든 부분 수열(subsequence)의 너비를 각각 구한 뒤, 그 합을 계산하는 것이 목표입니다. 단, 결과 값이 매우 커질 수 있으므로 109+7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 nums = [7, 4, 9]라고 해보겠습니다. 만들 수 있는 부분 수열은 [7], [4], [9], [7, 4], [7, 9], [4, 9], [7, 4, 9]이고, 각 수열의 너비는 차례대로 0, 0, 0, 3, 2, 5, 5입니다. 따라서 전체 너비의 합은 15가 됩니다.
접근 방법
모든 부분 수열을 직접 생성하면 지수 시간이 걸리므로 비효율적입니다. 대신 다음과 같은 수학적 아이디어를 활용할 수 있습니다.
- 리스트를 먼저 오름차순으로 정렬합니다.
- 정렬된 상태에서 인덱스
i의 원소nums[i]는, 자신보다 작거나 같은 앞쪽 원소들로 이루어진 부분 집합(2i가지)과 함께 있을 때 최댓값 역할을 합니다. - 반대로 뒤쪽 원소들(2n-1-i가지)과 함께 있을 때는 최솟값 역할을 합니다.
- 따라서 각 원소의 순기여(최댓값일 때)와 음기여(최솟값일 때)를 누적하면 전체 너비의 합을 선형 시간에 구할 수 있습니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- m := 109 + 7
- 리스트 nums를 오름차순으로 정렬
- ans := 0 으로 초기화
- nums 길이 + 1 크기의 power 리스트를 1로 채워 생성
- i를 1부터 len(nums)까지 반복하며 power[i] := power[i-1] * 2 mod m 계산 (2의 거듭제곱 미리 저장)
- i를 0부터 len(nums)-1까지 반복하면서:
- positive := (power[i] - 1) * nums[i] (nums[i]가 최댓값일 때의 기여)
- negative := (power[len(nums) - i - 1] - 1) * nums[i] (nums[i]가 최솟값일 때의 기여)
- ans := (ans + positive - negative) mod m
- ans 반환
파이썬 구현 예시
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums):
m = 10**9 + 7
nums.sort()
ans = 0
power = [1] * (len(nums) + 1)
for i in range(1, len(nums) + 1):
power[i] = power[i - 1] * 2 % m
for i in range(0, len(nums)):
positive = (power[i] - 1) * nums[i]
negative = (power[len(nums) - i - 1] - 1) * nums[i]
ans = (ans + positive - negative) % m
return ans
ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))
입력
[7, 4, 9]
출력
15
복잡도 분석
정렬에 O(n log n), 메인 반복문에 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 2의 거듭제곱을 저장하는 배열 때문에 O(n)입니다. 덕분에 부분 수열을 하나씩 열거하는 지수 시간 방식보다 훨씬 효율적으로 문제를 해결할 수 있습니다.