(Easy - DP) Leetcode - 303. Range Sum Query - Immutable

이 문제는 정수 배열이 NumArray 클래스를 초기화할 때 주어지면 이를 사용해 NumArray 클래스의 sumRange 함수를 완성하는 것 입니다.

sumRange함수는 정수 left, right가 주어지면 이를 index로 활용해 left <= right의 배열의 값들의 합을 반환해주는 함수입니다.

 

가장 간단하게 풀려면 매번 sumRange가 호출될 때마다 loop를 돌며 값의 합을 구하면 됩니다.

class NumArray {
public:
    NumArray(vector<int>& nums) :nums(nums) {
    }
    
    int sumRange(int left, int right) {
	int sum = 0;
        while (left <= right)
        	sum += nums[left++];
        return sum;
    }

    vector<int> nums;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

매번 범위 안에 있는 값들의 합을 구할 수 있지만 이러면 함수가 호출될 때마다 loop를 돌아야합니다.

이때 Dynamic Programming을 사용하면 최적화를 할 수 있습니다.

 

매번 값들의 합을 구하는 것이 아닌 NumArray 클래스가 초기화될 때 0번 index부터 i번째 index까지의 값들의 합을 미리 계산해 저장한 뒤 sumRange 함수가 호출되면 이 미리 계산한 값을 사용하는 것입니다.

미리 계산하기 위해 맨 처음 한 번만 loop를 돌면 되므로 sumRange의 시간복잡도가 O(1)이 될 수 있습니다.

 

class NumArray {
public:
    NumArray(vector<int>& nums) : preSum(nums.size()) {
        preSum[0] = nums[0];

	// 미리 index 0부터 index i까지의 합을 각 index i에 저장
        for (int i = 1; i < nums.size(); ++i) 
            preSum[i] = preSum[i - 1] + nums[i];
    }
    
    int sumRange(int left, int right) {
        if (left) // 만약 left가 0이 아니라면
            return preSum[right] - preSum[left - 1]; // left <= right 범위이므로 left - 1을 빼준다.
        return preSum[right]; // left가 0이라면 right까지의 합
    }

    vector<int> preSum; // 구간의 합을 저장할 배열
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */