[leetcode] Maximal Rectangle

·2024년 4월 13일
0

코딩

목록 보기
27/45

문제

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

풀이

풀기 전

  • 풀 방법을 이리저리 찾아보다가 뭔가 값을 누적해서 풀 수 있을 거 같았다. 그러고 아래 규칙을 찾았다.
    • 초기 matrix
      1 0 1 0 0
      1 0 1 1 1
      1 1 1 1 1
      1 0 0 1 0
    • 각 행의 값을 누적한다. 1이 연속적으로 나올 때만 누적하고, 0이 나올 때는 리셋한다.
      1 0 1 0 0
      1 0 1 2 3
      1 2 3 4 5
      1 0 0 1 0
    • 각 값은 좌측으로부터 연속적인 1의 개수를 의미한다. 그래서 특정 위치에 있는 값과 그 아래에 있는 값 중 작은 값이 의미하는 건 두 위치가 공통으로 갖는 좌측으로부터 연속적인 1의 개수이다. 예를 들어 (1, 4) 위치에 있는 3과 그 아래 (2, 4) 위치에 있는 5를 함께 보면, 둘 중 작은 수는 3이다. 즉, 두 위치 모두 좌측으로부터 1이 세번 연속으로 나온다는 의미이다. 그럼 넓이는 3이고 높이는 2인 직사각형이 존재하는 걸 알 수 있다. 이런 식으로 matrix를 순회해서 모든 직사각형을 파악할 수 있다.

코드

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];

		// 각 행의 연속적인 1을 누적해서 저장한다.
        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)  // 값이 0이면 0을 넣는다.
                    rowAcc[i][j] = 0;
                else  // 0이 아니면 누적해서 넣는다.
                    rowAcc[i][j] = rowAcc[i][j-1] + Character.getNumericValue(matrix[i][j]);
            }
        }

		// 누적한 값을 순회한다. 누적 값이 0이 아니면, 아래로 내려가면서 직사각형을 찾는다.
        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]);  // 이제까지 만난 값들이 중복으로 갖는 연속적인 1의 개수를 찾는다.
                    ans = Math.max(ans, h * w);  // 찾은 직사각형으로 정답을 갱신한다.
                }
            }
        }
        return ans;
    }
}

푼 후

  • 어떻게 풀긴 했는데 제약 조건이 약해서 풀린 거 같다. matrix 크기가 n * m이라고 하면, 반복문 세개가 겹쳐서 시간 복잡도는 O(n^2 * m)이다. 누적 값 저장하는 배열이 있어서 공간 복잡도는 O(n * m)이다.
  • 다른 사람 코드를 보니 DP 사용한 거 같던데.. 두려워서 보진 못했다.
profile
개발 일지

0개의 댓글