LeetCode [1508]: Range Sum of Sorted Subarray Sums

📌 LeetCode [1508]: Range Sum of Sorted Subarray Sums

🔗 문제 링크

---

문제 설명 📄

주어진 배열 nums에서 모든 부분합을 계산하고, 이를 오름차순으로 정렬했을 때 left번째부터 right번째까지의 부분합의 합을 반환해야 합니다. 결과는 10**9 + 7로 나눈 나머지를 반환합니다.

---

문제 접근 방식 🔍

1. 부분합 계산과 정렬:
   • 배열에서 모든 부분합을 계산하면 시간 복잡도는 O(n²)입니다.
   • 이후 이를 정렬하여 특정 구간만 선택하면 추가적으로 O(n² x log(n²))의 비용이 발생합니다.
2. 효율적인 부분합 계산:
   • 최소힙을 활용하여 가장 작은 부분합부터 정렬된 순서로 처리합니다.
   • 힙 연산으로 시간 복잡도를 O(n² x log(n))로 줄일 수 있습니다.

---

Solution 💻

import heapq

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MOD = 10**9 + 7
        heap = []

        for i in range(len(nums)):
            heapq.heappush(heap, (nums[i], i))
        
        answer = 0
        k = 0
        
        while heap:
            value, index = heapq.heappop(heap)
            k += 1
            
            if k > right:
                break
            if k >= left:
                answer += value
                answer %= MOD
            
            if index + 1 < len(nums):
                heapq.heappush(heap, (value + nums[index + 1], index + 1))
        
        return answer

---

시간 복잡도 분석 ⏲️

• 힙 초기화: 배열 길이 nn만큼 각 요소를 힙에 추가 → O(n x log(n)).
• 힙 정렬 및 합산: n2n²개의 모든 부분합을 힙에서 처리 → O(n² x log(n)).
• 총 시간 복잡도: O(n² x log(n)).

---

공간 복잡도 분석 🗄️

• 힙 사용 공간: 최대 O(n)개의 요소를 힙에 저장.
• 총 공간 복잡도: O(n).