[LeetCode] 303. Range Sum Query - Immutable

문제 출처: https://leetcode.com/problems/range-sum-query-immutable/

Range Sum Query - Immutable - LeetCode

---

문제

정수 배열 nums가 주어지면, 다음 유형의 다양한 질의를 처리해야 한다:

1. left <= right 인 left 와 right 인덱스 사이의 nums 값의 합을 계산하라.

NumArray 클래스를 구현하라:

• NumArray(int[] nums): nums를 기반으로 객체를 초기화
• int sumRange(int left, int right): left와 right 사이의 nums 값의 합을 반환(i.e. nums[left] + nums[left+1] + ... + nums[right])

 

예제

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

---

풀이

단순하게 생각해서 최초로 주어지는 nums를 저장하고 있다가, left와 right가 주어지게 되면 저장한 배열을 이용하여 left에서 right까지의 합을 계산할 수 있다.

var NumArray = function(nums) {
    this.nums = nums.slice();
};

NumArray.prototype.sumRange = function(left, right) {
    let answer = 0;
    for (let i = left; i <= right; i++) { answer += this.nums[i]; }
    return answer;
};

이 알고리즘은 sumRange 함수가 호출될 때마다 right-left+1 만큼의 반복이 수행될 것이다.

 

Prefix Sum을 이용하게 되면 최초 객체가 생성될 때, nums의 사이즈만큼의 반복이 필요한 대신에 sumRange가 호출될 때는 단순 산술 계산만으로 원하는 값을 얻을 수 있다. 어떻게 이것이 가능할까?

 

"Prefix Sum = 누적 합"이라는 이름에서 유추할 수 있는 것처럼, 최초 객체를 생성할 때 저장하는 것이 nums 배열이 아니라 nums 배열의 누적 합을 저장한다. 이때 누적 합이란 0 인덱스부터 i 인덱스까지의 합을 말한다.

var NumArray = function(nums) {
    this.prefix = [nums[0]];	// nums.length > 1
    
    for (let i = 1; i < nums.length; i++) {
    	this.prefix[i] = this.prefiex[i-1] + nums[i];
    }
}

위와 같이 누적합이 존재할 때, 특정 구간의 합은 prefix[right] - prefix[left-1] 과 같이 단술 산술로 계산 가능하다. 다음과 같은 그림을 생각해보자.

위 그림에서 빨간 선과 남색 선이 의미하는 것이 누적 합산의 값이다. 여기서 left와 right 사이의 구간을 알고 싶다면 당연히 right 위치에서 left-1 위치를 빼면 될 것이다. left-1 지점을 빼는 이유는 left에 대한 prefix는 left 자신의 값을 포함하고 있기 때문이다.

NumArray.prototype.sumRange = function(left, right) {
    return this.prefix[right] - (left-1 < 0 ? 0 : this.prefix[left-1]);
};

 

 

Github: 303.js

GitHub - opwe37/Algorithm-Study