[Leetcode] 1480. Running Sum of 1d Array

저번 주말은 장인어른 생신도 있고, 처남네가 집에 와있었던터라 공부를 못했다... 뭐... 할 시간이 있었지만, 안했던 것이니 반성하면서 다시 또 월요일을 열어본다. 인터뷰가 머지 않았다고!

 

May Leetcode Challenge 2021 에서 5월 3일에 (PST) 출시된 문제를 풀어보도록 하겠다.

 

문제는 아래 링크를 참고하길 바란다.

leetcode.com/problems/running-sum-of-1d-array/

Running Sum of 1d Array - LeetCode

 

주어진 nums 배열에서 runningSum[i] = sum(nums[0] + ... + nums[i]) 라고 정의한다면, nums의 running sum을 묻는 문제이다. 딱히 함정도 없어보이고, 생각나는대로 그냥 풀면 되는 문제 같다.

어차피 한 번 탐색으로 끝날 것 같고, 특정한 값들을 찾는다기 보다는 전체를 구해야 알 수 있는 부분이기 때문에 O(n) 정도로 구할 수 있으면 될 것 같아서이다.

 

그 와중에 또 in-place로 풀 것이냐 말 것이냐에서 두 가지 풀이가 나올 수 있을 것 같았다.

우선 출력 배열을 선언한 풀이를 보자.

class Solution {
    public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length]; // 주어진 입력배열과 동일한 크기로 선언
        result[0] = nums[0]; // 첫번째 값은 더할게 없으므로 동일함
        for (int i  = 1; i < nums.length; i++) { // 첫번째는 넣었으니 두번째부터 반복 시작
            result[i] = result[i - 1] + nums[i]; // 이전에 더해진 결과로 i 번째의 runningSum 을 구할 수 있음
        }
        
        return result;
    }
}

간단하기 때문에 설명은 생략하도록 하겠다.

바로 이어서 in-place 풀이 방법을 보겠다.

class Solution {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) { // 배열의 첫번째는 더해줄것이 없으므로 패스, 두번째부터 시작
            nums[i] += nums[i - 1]; // 이전 값에 자신을 더해주면 그것이 runningSum
        }
        
        return nums;
    }
}

아마 한두줄로 푼 사람들도 많을 것 같다.

 

두 개 풀이 모두 시간복잡도는 배열을 한 번 탐색하는 것으로 끝이니, 배열의 사이즈가 n 이라고 하면, $O(n)$ 이 된다.

문제는 공간복잡도인데, 공간복잡도는 예상했겠지만 위의 풀이법은 n 만큼 새로운 배열을 선언했으니 $O(n)$ 이 되고, 아래의 풀이법은 in-place 로 수정하면서 만들었기 때문에 $O(1)$ 이 된다.

그러므로 인터뷰에서 위의 풀이법을 사용해서 풀었다고 하더라도, 아래의 풀이법을 강요(!?)당할 수 있다.

 

어렵지 않으므로 여기서 넘어가겠다.