1314. Matrix Block Sum

문제: https://leetcode.com/problems/matrix-block-sum/

Matrix Block Sum - LeetCode

 2d vector에서 특정 구간의 합을 구하는 문제다.  k값이 주어지고, 2d vector 안의 (y,x) 포인트에서 i - k <= r <= i + k의 부분합을 모두 구한다.

 

class Solution {
public:
    
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int pSums[101][101];
        memset(pSums, 0, sizeof(pSums));
        
        int lenY = mat.size();
        int lenX = mat[0].size();
        
        for(int i = 0; i < lenY; i++){
            int prev = 0;
            for(int j = 0; j < lenX; j++){
                pSums[i + 1][j + 1] = pSums[i][j + 1] + prev + mat[i][j];
                prev += mat[i][j];
            }
        }
        
        for(int i = 0; i < lenY; i++){
            for(int j = 0; j < lenX; j++){
                int lessI = (i - k) < 0 ? 0 : i - k;
                int lessJ = (j - k) < 0 ? 0 : j - k;
                
                int moreI = (i + k) >= lenY ? lenY - 1 : i + k;
                int moreJ = (j + k) >= lenX ? lenX - 1 : j + k;
                
                mat[i][j] = pSums[moreI + 1][moreJ + 1] + pSums[lessI][lessJ]
                    - pSums[moreI + 1][lessJ] - pSums[lessI][moreJ + 1];
            }
        }
        return mat;
    }
};

 포인트는 2d vector의 부분합을 구할 때 vector를 사용하면 공간효율이 떨어져서 2d array를 사용하고 global scope에 선언해서 초기화 과정을 생략하거나 local scope에 두고 memset을 사용해서 0으로 초기화해주면된다.

 부분합을 구했으면 각 (y, x)에서 부분합을 구할 구간을 정하고 2d에서 부분합을 구하는 방법을 사용해주면된다.

 

mat[i][j] = pSums[moreI + 1][moreJ + 1] + pSums[lessI][lessJ] - pSums[moreI + 1][lessJ] - pSums[lessI][moreJ + 1];

 

 range sum query와 동일한 내용인데 (i2, j2)까지 부분합이 구해져있으므로 (i2, j1 - 1)과 (i1 - 1, j2)를 빼주고 (i1 - 1, j1 - 1)을 더해주면 (i1, j1) ~ (i2, j2) 구간의 합이 구해진다.