안녕하세요 !
오늘은 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차원 배열이라서 솔루션이 바로 명확하게 떠오르진 않았지만, 나름 깔끔한 방법으로 해결한 것 같습니다!
이번 포스팅도 읽어주셔서 감사합니다 :)