leetcode/ 1480. Running Sum of 1d Array

Description

Running Sum of 1d Array - LeetCode

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.

---

Process

리스트를 사용하는 기초적인 문제다. 되게 간단한 문제였는데 생각을 돌아돌아 해서 삽질 좀 했다. 블로깅을 다시 시작하게 된 결정적인 계기.

 

1. 입력 범위 확인

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

 

시간 복잡도에 영향을 미치는 것은 nums.length이고 범위는 10^3으로 O(n^2)으로 풀어도 관계없다.

 

---

Trial: Time: 45 ms (37.94%), Space: 14 MB (64.21%)

class Solution:
	def runningSum(self, nums: list[int]) -> list[int]:
    	ans = [0] * len(nums)
        ans[len(ans) - 1] = sum(nums)
        for i in range(len(nums) - 2, -1, -1):
        	ans[i] = ans[i + 1] - nums[i+ 1]
        return ans

 

쓸데없이 합을 구하고 싶은 욕구가 심하게 들었다. 하지만 사람은 문제를 잘 읽어야 한다...... 이렇게 풀면 쓸데없는 리스트 생성과 쓸모없는(어차피 반복문 안에서 구해지는) 전체 합 sum() 함수를 호출한다. 부분합 사용이 전혀 필요 없고 단지 리스트를 순회하면서 각 요소를 더해주면 된다.

---

Solution: Time: 32 ms (97.13%), Space: 14.1 MB (64.21%) - LeetHub

class Solution:
	def runningSum(self, nums: list[int]) -> list[int]:
    	for i in range(1, len(nums)):
        	nums[i] += nums[i - 1]
        return nums

 

그냥 리스트를 인덱스 1부터 순회하면서 이전의 요소를 더한 값을 저장하도록 구현하면 된다. 말했듯이 기초 중의 기초적인 문제였고, 리스트 사용 확인 문제 정도였던 것 같다.

---

Conclusion

문제 파악을 잘해야겠다. 요구사항을 잘 읽고 목표하는 답을 위한 최적의 코드를 짜는 것에 집중하자.