99클럽 코테스터디 22일차 TIL Maximal Rectangle

Maximal Rectangle

LeetCode Hard DP

문제 설명

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

문제 풀이

문제 설명을 보면 굉장히 간단하다. 주어진 배열에서 가장 큰 직사각형을 뽑아내면 되는 문제다.

 

처음에는 직사각형을 고려하지 않고 정사각형의 형태가 연속으로 있는 경우만 고려해서 틀렸다.

class Solution {
public:
    bool arr[201][201] = {false, };
    int dir[3][2] = {{0, 1}, {1, 0}, {1, 1}};
    int col, row, ret=0;
    bool flg;

    bool condition(int x, int y) {
        return 0 <= x && x < row && 0 <= y && y < col;
    }

    int ckRec(int x, int y, vector<vector<char>>& mat) {
        queue<pair<int, int>> q;
        int res = 1;

        q.push(make_pair(x, y));
        arr[x][y] = true;

        while (!q.empty()) {
            int nx = q.front().first;
            int ny = q.front().second;
            q.pop();

            int cnt = 0, cnt2=0;
            for (int i=0; i<3; i++) {
                int dx = nx + dir[i][0];
                int dy = ny + dir[i][1];
                if (condition(dx, dy) && mat[dx][dy] == '1') {
                    cnt++;
                    cnt2 -= arr[dx][dy] ? 1 : 0;
                }
            }
            if (cnt == 3) {
                for (int i=0; i<3; i++) {
                    int dx = nx + dir[i][0];
                    int dy = ny + dir[i][1];
                    q.push(make_pair(dx, dy));
                    arr[dx][dy] = true;
                }
                res += cnt + cnt2;
            }
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        row = matrix.size();
        if (row == 0) return 0;
        col = matrix[0].size();

        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (matrix[i][j] == '1' && !arr[i][j]) ret = max(ret, ckRec(i, j, matrix));
            }
        }

        return ret;
    }
};

 

이 코드를 수정해서 한 변이 1인 직사각형 까지 고려하기에는 너무 많은걸 바꿔야 해서 처음부터 다시 설계하다가 포기하고 답을 찾아봤다.

 

리트코드는 문제 바로 옆에 Discuss를 누르면 다른 답을 찾아볼 수 있어서 편리했다.

 

다른 유저의 아이디어를 아무리 읽어봐도 이해가 되질 않아서 코드를 봤지만, 코드를 봐도 잘 이해가 안됐고, 거의 1시간 가까이 그 코드만 뜯어봤던 것 같다.

 

참고한 코드와 설명 링크

 

코드

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& mat) {
        int i, j, cnt1, cnt2, res=0;
        int row=mat.size(), col=mat[0].size();
        if (row == 0) return 0;
        vector<vector<int>> arr(row, vector<int>(col));

        for (i=0; i<row; i++) arr[i][0] = mat[i][0] - '0';

        for (i=0; i<col; i++) arr[0][i] = mat[0][i] - '0';

        for (i=1; i<row; i++) {
            for (j=1; j<col; j++) {
                if (mat[i][j] == '1') arr[i][j] = min({arr[i][j-1], arr[i-1][j], arr[i-1][j-1]}) + 1;
            }
        }

        for (i=0; i<row; i++) {
            for (j=0; j<col; j++) {
                if (mat[i][j] == '1') {
                    cnt1 = arr[i][j] * arr[i][j];
                    cnt2 = arr[i][j] * arr[i][j];
                    for (int k=i+1; k<row && arr[i][j] <= arr[k][j] && arr[k][j]; k++) cnt1 += arr[i][j];
                    for (int l=j+1; l<col && arr[i][j] <= arr[i][l] && arr[i][l]; l++) cnt2 += arr[i][j];
                    res = max({cnt1, cnt2, res});
                }
            }
        }

        return res;
    }
};

 

첫번째, 두번째 for 문에서 새로운 배열에 1 과 0 의 형태로 저장해준다.

 

세번째 for 문은 왼쪽이나 위쪽, 대각선 왼쪽 위로의 정사각형의 크기들을 순회하며 확인하는 작업을 거쳐 dp 방식으로 저장해주는 코드이다.

 

마지막 2중 for 문에서는 최대 직사각형의 크기를 구하는데, cnt1, cnt2 는 각각 아래 방향과 오른쪽 방향으로 확장할 수 있는 만큼 확장해 최대면적을 계산해 마지막에 res 값과 비교하여 더 큰 값을 저장한다.

회고

오랫만에 알고리즘에 3시간 이상 소모한 날이다.

 

할만한 문제가 풀이를 보니까 안 할만해서 솔직히 벽느낀거 같다.

 

gpt 한테 코드 주고 최적화의 여지가 있냐고 물어보니까 있다고 해서 어이가 없었다. 완벽해 보이는 코드였는데, 유의미하게 시간을 단축시켜줬다.

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& mat) {
        if (mat.empty()) return 0;

        int row = mat.size();
        int col = mat[0].size();
        vector<int> heights(col, 0);
        int maxArea = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

private:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);
        int maxArea = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        heights.pop_back();
        return maxArea;
    }
};

 

스택을 이용해서 풀이하는 거라는데 솔직히 머리에 안들어와서 그냥 제출만 해봤다.

 

GPT 의 코드설명

코드 설명 heights 배열 사용:
- 각 행에 대해 히스토그램의 높이를 계산합니다.

- mat[i][j] == '1'이면, heights[j]의 높이를 1 증가시키고,
    mat[i][j] == '0'이면 해당 열의 높이를 0으로 초기화합니다.

largestRectangleArea 함수:
- 이 함수는 스택을 사용하여 주어진 히스토그램에서 가장 큰 직사각형의 면적을 구합니다.

- 스택에는 히스토그램의 인덱스를 저장하고, 현재 높이보다 낮은 높이를 만나면
    스택에서 값을 꺼내면서 직사각형 면적을 계산합니다.

- 이 방법은 히스토그램의 각 높이에 대해 정확히 한 번씩만 계산하기 때문에
    시간 복잡도가 O(n)으로 효율적입니다.


전체 알고리즘:
- 각 행에 대해 히스토그램의 높이를 계산한 후, 
    largestRectangleArea를 호출하여 현재까지의 최대 직사각형 면적을 갱신합니다.

- 전체 시간 복잡도는 O(n * m)으로, n은 행의 수, m은 열의 수입니다.