문제
- 문제 링크
- 0과 1로 채워진 2차원 배열
matrix
가 주어진다. 1로만 채워진 직사각형 영역 중 가장 큰 영역의 넓이를 구해야 한다.
- 제약 조건
- 배열 길이:
1 <= matrix.length, matrix[0].length <= 200
- 예시

풀이
풀기 전
- 풀 방법을 이리저리 찾아보다가 뭔가 값을 누적해서 풀 수 있을 거 같았다. 그러고 아래 규칙을 찾았다.
코드
class Solution {
public int maximalRectangle(char[][] matrix) {
int ans = 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] rowAcc = new int[rows][cols];
for (int i=0; i<rows; i++) {
rowAcc[i][0] = Character.getNumericValue(matrix[i][0]);
for (int j=1; j<cols; j++) {
int num = Character.getNumericValue(matrix[i][j]);
if (num == 0)
rowAcc[i][j] = 0;
else
rowAcc[i][j] = rowAcc[i][j-1] + Character.getNumericValue(matrix[i][j]);
}
}
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
if (rowAcc[i][j] == 0)
continue;
int h = 0;
int w = Integer.MAX_VALUE;
for (int k=i; k<rows && rowAcc[k][j] != 0; k++) {
h++;
w = Math.min(w, rowAcc[k][j]);
ans = Math.max(ans, h * w);
}
}
}
return ans;
}
}
푼 후
- 어떻게 풀긴 했는데 제약 조건이 약해서 풀린 거 같다.
matrix
크기가 n * m
이라고 하면, 반복문 세개가 겹쳐서 시간 복잡도는 O(n^2 * m)
이다. 누적 값 저장하는 배열이 있어서 공간 복잡도는 O(n * m)
이다.
- 다른 사람 코드를 보니 DP 사용한 거 같던데.. 두려워서 보진 못했다.