99클럽 코테 스터디 22일차 TIL [DP]

- 오늘의 학습 키워드 : DP

[문제 이름 :   정수 삼각형 (LeetCode - DP, Lv 3) ]

문제 url : https://leetcode.com/problems/maximal-rectangle/

 

 

내가 작성한 코드는 아래와 같다.

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxRectangle = 0;

        for(int i=0; i<rows; i++) {
            for(int j=0; j<cols; j++) {
                if(matrix[i][j] == '0') continue;
                maxRectangle = Math.max(maxRectangle, getRectangle(matrix, i, j, rows, cols));
            }
        }
        return maxRectangle;
    }

    static int getRectangle(char[][] matrix, int x, int y, int rows, int cols) {
        int area = 0;
        int maxWidth = cols;

        for(int i=x; i<rows; i++) {
            int width = 0;
            while(y + width < maxWidth && matrix[i][y + width] == '1') {
                width++;
            }

            maxWidth = Math.min(maxWidth, y + width);
            int height = i - x + 1;
            int tmpArea = (maxWidth - y) * height;
            area = Math.max(area, tmpArea);
        }
        return area;
    }
}

[풀이 과정]

1. 완전탐색을 돌리면서, 1을 가진 x,y를 찾는다.

2. 최대 너비 maxWidth를 matrix[0].length;로 초기화한다. 이는 이전 행까지 고려했을 때, 가능한 최대 직사각형의 너비를 유지하는 변수를 의미한다.
3. width는 현재 행에서 y열에서 시작하여 연속된 1의 개수를 세는 변수이다.

4. for(int i=x; i<rows; i++)에서 for문을 돌며 행을 따라 아래로 내려가면서 직사각형을 확장시켜 본다.

5. while (y + width < maxWidth && matrix[i][y + width] == '1') { width++; } 코드의 의미는, 현재 행에서 'y'열부터 시작해 연속된 1의 개수를 세는 것을 의미한다. 이는 계산하는 직사각형의 너비 길이를 의미한다.

풀이 시간 : 50분

 

[참고]

해당 문제는 여러 풀이법이 있는 것으로 보인다. 이에 다른 풀이 방안도 소개해보고자 한다. 크게 두 가지 풀이 방법이 있다.

1. 히스토그램 방식으로 변환하여 문제를 바라보기.

2. DP를 사용하여 각 셀에서 최대 직사각형의 면적을 계산해보기.

 

1. 히스토그램 방식으로 변환하여 문제를 바라보기

히스토그램에서 최대 직사각형을 찾는 문제는 스택을 이용하여 해결할 수 있다.

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return 0;
    }

    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] height = new int[rows][cols];

    // 높이 계산
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == '1') {
                height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
            } else {
                height[i][j] = 0;
            }
        }
    }

    // calculate the max rectangle row by row
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
        maxArea = Math.max(maxArea, maxAreaInHist(height[i]));
    }

    return maxArea;
}

public int maxAreaInHist(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int max = 0;

    for (int i = 0; i <= height.length; i++) {
        int cur = i == height.length ? -1 : height[i];
        while (!stack.isEmpty() && cur < height[stack.peek()]) {
            int h = height[stack.pop()];
            int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
            max = Math.max(max, w * h);
        }
        stack.push(i);
    }

    return max;
}

1. height[i][j] 배열을 사용하여 각 셀에서 연속된 '1'의 높이를 계산한다.

2. 첫 번째 행의 경우, height[i][j]는 그 자체로 1이거나 0이다. 두 번째 행부터는 matrix[i][j]가 1인 경우에는 해당 셀 위의 값에 1을 더하여 heights[i][j]를 계산한다.

3. 각 행에 대해 히스토그램 heights[i]를 기반으로 최대 직사각형의 면적을 계산한다.

4. 히스토그램에서 각 막대(열)을 순차적으로 처리하며, 스택에 인덱스를 저장한다. 현재 막대보다 낮은 막대를 만나면, 스택에서 막대를 하나씩 꺼내면서 직사각형의 높이와 너비를 계산하고, 최대 면적을 갱신한다.

 

2. DP 사용하기

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0
                || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }

        final int rows = matrix.length;
        final int cols = matrix[0].length;
        int[] left = new int[cols];
        int[] right = new int[cols];
        int[] height = new int[cols];
        // 현재 행에서 각 열에 대해 최대한 왼쪽 경계 계산
        Arrays.fill(left, 0);
        // 현재 행에서 각 열에 대해 최대 오른쪽 경계를 게산
        Arrays.fill(right, cols);
        // 각 열에서 1로 구성된 최대 높이를 기록하는 배열
        Arrays.fill(height, 0);

        int maxA = 0;
        for (int i = 0; i < rows; i++) {
            int cur_left = 0, cur_right = cols;
            // 높이 계산
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                }
                else {
                    height[j]=0;
                }
            }
            // 왼쪽 경계 계산
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    left[j]=Math.max(left[j], cur_left);
                }
                else {
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            // 오른쪽 경계 계산
            for (int j = cols - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], cur_right);
                }
                else {
                    right[j] = cols;
                    cur_right = j;
                }
            }
            // 전체 면적 계산
            for (int j = 0; j < cols; j++) {
                maxA = Math.max(maxA, (right[j] - left[j]) * height[j]);
            }
        }

        return maxA;
    }
}

1. height, left, right배열을 만들어서 각각 최대 높이를 저장하는 배열, 왼쪽 경계 / 오른쪽 경계를 저장하는 배열을 생산한다.

2. 이후 각 셀에서 (right[j] - left[j]) * height[j]를 통해 가능한 최대 직사각형의 면적을 구하고, 이를 최대값과 비교하여 갱신한다.

 

 

내일은 유니온 파인드 알고리즘을 사용하는 백준 문제들을 풀어보려고 한다.