[LeetCode] 1480. Running Sum of 1d Array(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

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.

 

 

[제한 사항]

 

 

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

 

 

[입출력 예]

 

 

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]

 

 

[문제 풀이]

 

 

앞으로 프로그래머스, 백준, Softeer 문제뿐만이 아니라 LeetCode 문제도 풀어볼 예정이다.

LeetCode는 Day 별로 풀어야할 문제가 정해져있어서 좋은 것 같다.

 

이 문제는 누적 합 알고리즘(Prefix Sum)에 속한다.

그리고 기초적인 문제지만 어느 문제를 풀 때 내용을 활용하여 쓸 수 있기 때문에 기초를 단단히 해야한다.

 

 

아무튼 문제 풀이법을 설명하자면 배열이 주어지면 배열 원소들의 누적된 합을 차례대로 저장하는 것이다.

 

예를 들어 주어진 배열에 1, 3, 5, 7의 값이 있다고 가정해보자.

 

먼저 원소 1에 접근하고 누적 값 변수에 1을 더한다.

현재 누적 값(1)을 배열에 저장한다.

 

다음 원소 3에 접근하고 누적 값 변수에 3을 더한다.

현재 누적 값(4)를 배열에 저장한다.

 

다음 원소 5에 접근하고 누적 값 변수에 5를 더한다.

현재 누적 값(9)를 배열에 저장한다.

 

다음 원소 7에 접근하고 누적값 변수에 7를 더한다.

현재 누적 값(16)을 배열에 저장한다.

 

 

최종적으로 누적 값이 저장된 배열은 1, 4, 9, 16이 저장된다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/LeetCode: LeetCode for Coding Test

 

 

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> answer;
        int sum = 0;
        for(int element : nums) {
            sum += element;
            answer.emplace_back(sum);
        }
        return answer;
    }
};