문제 이해하기
숫자 리스트 nums가 주어졌을 때, 가능한 모든 연속된 부분 배열(contiguous subarray)을 고려합니다. 각 부분 배열의 합을 계산한 뒤 이 값을 모두 더하고, 최종 결과를 10⁹ + 7(1,000,000,007)로 나눈 나머지를 반환하는 것이 목표입니다.
예를 들어 입력이 nums = [3, 4, 6]이라면 다음과 같은 부분 배열들이 존재합니다.
[3], [4], [6], [3, 4], [4, 6], [3, 4, 6]
각 부분 배열의 합은 순서대로 3, 4, 6, 7, 10, 13이며, 이를 모두 더하면 43이 됩니다.
효율적인 접근 방법
모든 부분 배열을 실제로 생성해 합을 구하면 O(N²)의 시간이 걸리지만, 수학적 아이디어를 활용하면 O(N) 만에 해결할 수 있습니다.
핵심은 각 원소가 전체 합에 기여하는 횟수를 세는 것입니다. 인덱스 i에 있는 원소 nums[i]는 시작 지점이 i 이전 또는 i이고 끝 지점이 i 이후 또는 i인 모든 부분 배열에 포함됩니다.
- 시작 지점 후보: 0 ~ i → 총 (i+1)개
- 끝 지점 후보: i ~ N-1 → 총 (N-i)개
따라서 nums[i]는 정확히 (i+1) × (N-i)개의 부분 배열에 등장하며, 해당 원소의 전체 기여도는 (i+1) × (N-i) × nums[i]가 됩니다. 이 값을 모든 원소에 대해 더하면 원하는 답을 얻을 수 있습니다.
알고리즘 단계
- N := nums의 크기
- ans := 0
- i를 0부터 nums 크기 미만까지 반복:
- n := nums[i]
- ans := ans + (i+1) * (N-i) * n
- (ans mod 1000000007) 반환
구현 예제
class Solution:
def solve(self, nums):
N = len(nums)
ans = 0
for i in range(len(nums)):
n = nums[i]
ans += (i+1) * (N-i) * n
return ans % 1000000007
ob = Solution()
print(ob.solve([3, 4, 6]))
입력
[3, 4, 6]
출력
43
동작 검증
nums = [3, 4, 6]일 때 각 원소의 기여도를 직접 계산해 보면 다음과 같습니다.
- 인덱스 0 (값 3): 1 × 3 × 3 = 9
- 인덱스 1 (값 4): 2 × 2 × 4 = 16
- 인덱스 2 (값 6): 3 × 1 × 6 = 18
9 + 16 + 18 = 43으로, 예상 출력과 일치합니다.
복잡도 분석
리스트를 한 번만 순회하므로 시간 복잡도는 O(N)이며, 추가 저장 공간 없이 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다.