304. Range Sum Query 2D - Immutable - 데일리 문제

304. Range Sum Query 2D - Immutable

난이도: Medium

---

Given a 2D matrix matrix, handle multiple queries of the following type:

• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

 

Example 1:

 

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 104 calls will be made to sumRegion.

문제 설명

왼쪽 위 모서리(row1, col1)와 오른쪽 아래 모서리(row2, col2)의 좌표가 주어질 때  사각형 내부의 행렬 요소의 합을 계산하는 문제입니다.

 

문제 접근법

처음에는 단순하게 이중 포문을 순회하면서 행렬의 합을 리턴하였습니다, 결과는 통과는 되지만 시간이 엄청 걸리는 결과가 나왔습니다. 

 

이유는 겹치는 부분을 매번 중복하여 순회 하는 과정에서 많은 시간이 소요된 거 같습니다.

 

그래서 아래와 같이 DP 방법을 사용하여 미리 열의 값을 더해준 행을 초기해준 뒤 문제를 풀었습니다! 

 

 

코드

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return;
    this.dp = Array.from(Array(matrix.length + 1),()=>Array(matrix[0].length +1).fill(0))
    for (let r = 0; r < matrix.length; r++) {
        for (let c = 0; c < matrix[0].length; c++) {
            // 현재값에 이전까지 더한 값을 더 함
            this.dp[r][c + 1] = this.dp[r][c] + matrix[r][c];
        }
    } 
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
   let sum = 0 
   for(let row = row1; row <= row2; row++){
       // -this.dp[row][col1] (포함되지 않는 열의 값을 빼준다.)
       sum += this.dp[row][col2+1] - this.dp[row][col1]
   }
    return sum
};

/** 
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */