[Leet Code] 1480. Running Sum of 1d Array

문제 원본: https://leetcode.com/problems/running-sum-of-1d-array/

문제

한 개의 배열 nums가 주어진다. nums의 누적 합을 runningSum[i] = sum(nums[0] ... nums[i])의 배열로 정의하여 반환하라.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints:

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

접근 방법

두 개의 반복문

처음에는 반복문을 두 개 써서 i를 nums.length까지 돌게 하고, j를 i까지 돌게 했다. 그렇게 현재 인덱스까지 nums의 값을 합산해서 sum[i]에 할당했다. 그렇게 하니까 자바에서 메모리 사용률에 있어서는 상급인데, 실행 시간에 있어서는 최하를 찍어버렸다. 아래는 그 코드다.

class Solution {
    public int[] runningSum(int[] nums) {
        int[] sum = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= i; j++) {
                sum[i] += nums[j];
            }
        }
        return sum;
    }
}

이대로 “와 Accept 떴다” 하고 넘기기엔 찝찝해서 문제를 다시 보는데…

한 개의 반복문

그래서! 문제의 예시를 자세히 보니까 하나의 규칙을 발견했다. 바로 현재 sum[i]의 값은 sum[i - 1] + nums[i]라는 것이다. sum[0] = nums[0], sum[1] = sum[0] + nums[1]이 성립했다. 단, sum[0] = nums[0]은 따로 초기값을 세팅해줘야 하고, 반복문을 1부터 nums.length까지 돌아야 한다. 이 방법으로 “Your runtime beats 100.00% of java submissions.”를 받았다.

풀이

Java

class Solution {
    public int[] runningSum(int[] nums) {
        int[] sum = new int[nums.length];
        
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            sum[i] = sum[i - 1] + nums[i];
        return sum;
    }
}

• Runtime: 0ms
• Memory: 41.7MB

C#

public class Solution {
    public int[] RunningSum(int[] nums) {
        int[] sum = new int[nums.Length];
        
        sum[0] = nums[0];
        for (int i = 1; i < nums.Length; i++)
            sum[i] = sum[i - 1] + nums[i];
        return sum;
    }
}

• Runtime: 176ms
• Memory: 41.5MB

Python

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

• Runtime: 68ms

• Memory: 14.1MB

• 난 주어진 nums는 건드리면 안 된다고 생각했는데, 상위권 유저들 보니까 nums 값을 바꿔서 반환하고 있었다. 그 편이 메모리도 덜 차지할테니까 훨씬 나을 것 같다(이것이 오개념..?).