[Leet Code] Range Sum Query 2D - Immutable

안녕하세요 !
오늘은 5월 2주차 5번째 알고리즘인 Range Sum Query 2D - Immutable 풀이를 적어보겠습니다.

문제

요약
주어진 matix 에서 범위의 왼쪽 상단의 row, column 과 오른쪽 하단의 row, column이 주어지면 그 범위 숫자의 합을 구해서 return 하는 문제입니다.

시도한 방법

이번에는 처음 생각한 방법으로 바로 Accept를 받았습니다. (진짜 발전했다 나)

matrix 가 주어지면 row 별로 누적 합을 저장했습니다.
예를 들어서 [[1, 2, 3], [4, 5, 6]] 형태의 matrix 라면 [[1, 3, 6], [4, 9, 15]] 로 바꾸어서 구해주었습니다.
주어진 범위의 합을 구할 때는 row 의 col2 요소에서 col1 - 1 요소를 빼서 더해주었습니다.

코드 설명

int[][] numMatrix;

public NumMatrix(int[][] matrix) {
    numMatrix = matrix;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
        }
    }
}

for문을 순회하면서, row 별로 누적 합을 차례대로 저장해서 numMatrix 를 만들어줍니다.

int result = 0;

return 할 result 변수를 초기화해줍니다.

for (int row = row1; row <= row2; row++) {
      if (col1 > 0) {
          result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
      } else {
          result += numMatrix[row][col2];
      }
  }

col1 이 0일 경우에는 굳이 col1 - 1 을 빼줄 필요가 없습니다.
그렇기 때문에 분기 처리를 꼭 해줘야 합니다.
col1 이 0이라면 각 row 별로 누적 합을 그대로 result에 더해줍니다.
col1 이 0이 아니라면 row 별 누적 합에서 col1 - 1 의 요소를 빼서 result 에 더해줍니다.
그리고, row1 과 row2 가 연속적이지 않을 경우에는 중간 row들도 더해주어야하기 때문에 for문을 순회합니다.

전체 코드

class NumMatrix {
    int[][] numMatrix;

    public NumMatrix(int[][] matrix) {
        numMatrix = matrix;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = 0;

        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
            } else {
                result += numMatrix[row][col2];
            }
        }

        return result;
    }
}class NumMatrix {
    int[][] numMatrix;

    public NumMatrix(int[][] matrix) {
        numMatrix = matrix;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = 0;

        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
            } else {
                result += numMatrix[row][col2];
            }
        }

        return result;
    }
}

마무리

2차원 배열이라서 솔루션이 바로 명확하게 떠오르진 않았지만, 나름 깔끔한 방법으로 해결한 것 같습니다!

이번 포스팅도 읽어주셔서 감사합니다 :)