[Leetcode]2574. Left and Right Sum Differences

문제 요약

• 알고리즘 분류:  누적합, 수학
• 난이도: Medium
• 문제내용:
  • 수 배열 nums가 주어진다.
  • leftSum[i]는 배열 nums에서 인덱스 i의 왼쪽에 있는 요소들의 합이다. 0번째 인덱스나 요소가 없으면 leftSum[i] = 0이다.
  • rightSum[i]는 배열 nums에서 인덱스 i의 오른쪽에 있는 요소들의 합이다.n-1번째 인덱스나 요소가 없으면 rightSum[i] = 0이다.
  • answer배열은 아래와 같이 정의한다.  answer를 반환 하여라
    •  answer[i] = |leftSum[i] - rightSum[i]|
• 사이트 주소: https://leetcode.com/problems/left-and-right-sum-differences/description/

문제풀이

 이번 문제는 완전탐색으로 풀면 O(N^2)나온다.문제의 최대 길이는 1000이라서 완전탐색으로 풀어도 통과가 되지만누적합을 이용하면 O(N)만큼 나온다. 그래서 이번 문제는 구간합, 누접합을 이용한 풀이를 설명 할것이다. 구간합, 누적합대한 설명은 아래글을 참고 하면된다.

https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

누적합만 대한 지식만 알면 간단 하게 풀 수 있다. leftSum은 0번째 인덱스 0으로 지정 하고 1번째 부터 n-1번째 까지 leftNums[i] = nums[i - 1] + leftNums[i - 1] 식으로 풀면 된다.

rightSum[i]은 n-1번째 인덱스을 0으로 지정하고 n-2부터 0번까지 rightNums[i] = nums[i + 1] + rightNums[i + 1]식으로 풀면 된다

마지막으로 answer는 0번 부터 n-1까지 answer[i] = |leftSum[i] - rightSum[i]|식으로 진행하면 끝이다. 자세한것은 아래 코드를 보면 된다.

Code

Python

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        size = len(nums)
        left_nums = [0 for _ in range(size)]
        right_nums = [0 for _ in range(size)]

        # 왼쪽
        for i in range(1, size):
            left_nums[i] = nums[i - 1] + left_nums[i - 1]

        # 오른쪽
        for i in range(size - 2, -1, -1):
            right_nums[i] = nums[i + 1] + right_nums[i + 1]

        # 각 항목 최대값 추가
        result = [0 for _ in range(size)]
        for i in range(size):
            result[i] = abs(left_nums[i] - right_nums[i])

        return result

Java

class Solution {
    public int[] leftRightDifference(int[] nums) {
        int size = nums.length;
        int[] leftNums = new int[size];
        int[] rightNums = new int[size];

        // 왼쪽
        for (int i = 1; i < size; i++) {
            leftNums[i] = nums[i - 1] + leftNums[i - 1];
        }

        // 오른쪽
        for (int i = size - 2; i >= 0; i--) {
            rightNums[i] = nums[i + 1] + rightNums[i + 1];
        }

        // 각 항목 최대값 추가
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = Math.abs(leftNums[i] - rightNums[i]);
        }

        return  result;
    }
}

Javascript

var leftRightDifference = function(nums) {
    const size = nums.length;
    const leftNums = Array(size).fill(0);
    const rightNums = Array(size).fill(0);

    // 왼쪽
    for (let i = 1; i < size; i++) {
        leftNums[i] = nums[i-1] + leftNums[i - 1];
    }

    // 오른쪽
    for (let i = size - 2; i >= 0; i--) {
        rightNums[i] = nums[i + 1] + rightNums[i + 1];
    }

    const result = Array(size).fill(0);
    for (let i = 0; i < size; i++) {
        result[i] = Math.abs(leftNums[i] - rightNums[i]);
    }

    return result;
};