304. Range Sum Query 2D - Immutable Java 풀이

쉬운 풀이

class NumMatrix {
    // y1 x1 y2 x2
    //
    int[][] matrix;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        int x1 = Math.max(row1, row2);
        int x2 = Math.min(row1, row2);
        int y2 = Math.min(col1, col2);
        int y1 = Math.max(col1, col2);
        for(int i=x2; i<=x1; i++) {
            for(int j=y2; j<=y1; j++) {
                sum += matrix[i][j];
            }
        }
        return sum;
    }
}

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

 

 

아예 만들때 미리 계산하는 풀이

class NumMatrix {
    // 블록별 계산식을 미리 구해놓자
    // x축만 대상으로 간다면 (x1 -> x2 까지의 합)
        // 00 01 02 03 04 05
        // 11 12 13 14 15
        // 22 23 24 25
        // 이렇게 미리 구해둔 후에 이걸 합친다면?
        // matrix 를 만드는건 오래걸려도 상관 없다면 이게 sumRegion 에서는 효율적
    int[][][] matrix;


    public NumMatrix(int[][] matrix) {
        this.matrix = new int[matrix[0].length][matrix.length][matrix.length];

        for(int j=0; j<matrix[0].length; j++) {
            for(int i=0; i<matrix.length; i++) {
                for(int k=i; k<matrix.length; k++) {
                    for(int l=i; l<=k; l++) {
                        this.matrix[j][i][k] += matrix[l][j];
                    }
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        
        for(int i=col1; i<=col2; i++) {
            sum += this.matrix[i][row1][row2];
        }

        return sum;
    }
}

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

미리 구하는게 안됨!!

 

근데 어차피 미리 구하는거 자체는 맞긴 한데 방법의 차이로 보였다.

.

 

뭔가 위의 방식에서 조금 더 효율성을 챙길 방법을 고민해 보니 모든 경우를 다 구해놓을게 아니라, 사각형들을 구해놓고 계산하면 되지 싶었다.

누적합을 활용하는 것인데, 코드를 보는게 설명이 빠를듯.

 

class NumMatrix {
    int[][] prefix;

    public NumMatrix(int[][] matrix) {
        // 굳이 +1 을 해주는 이유는 위의 값을 구할 때 -1 을 해줘야되는데 그게 귀찮아서.
        prefix = new int[matrix.length + 1][matrix[0].length + 1];

        // 0,0 부터 시작하는 모든 사각형을 다 구해야 한다.
        // 이것도 누적합
        // 지금 matrix + 위의 사각형 + 왼쪽 사각형 - 위/왼쪽 사각형 겹치는 부분 = 지금까지의 사각형


        for(int i=0; i<matrix.length; i++) {
            for(int j=0; j<matrix[0].length; j++) {
                // 현재 matrix + 위쪽 + 왼쪽 - 겹치는거
                prefix[i+1][j+1] = matrix[i][j] + prefix[i+1][j] + prefix[i][j+1] - prefix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 0,0부터 최종 범위까지 구해서 - 위쪽 사각형 빼고 - 왼쪽 사각형 빼고 + 둘다 빠진부분 더하면 됨
        return prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1];
    }
}

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