[LeetCode] 1727. Largest Submatrix With Rearrangements

https://leetcode.com/problems/largest-submatrix-with-rearrangements/description/

Largest Submatrix With Rearrangements - LeetCode

leetcode - Largest Submatrix With Rearrangements

문제 유형 : 정렬 / 부분합

문제 난이도 : Medium

 

 

문제

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

 

당신은 m * n의 크기의 바이너리 행렬을 받는다.

당신은 행렬을 열별로 재배열 할 수 있다.

재배열하여 모든 요소가 1인 부분행렬의 최대 크기를 구하시오.

 

 

풀이

이 문제는 열 내부에서 행을 한 칸씩 내려가면서 부분합을 구하고, 그 부분합들이 만드는 가장 큰 사각형을 찾으면 된다.

높이를 쌓아가는 과정에서 0을 만나면, 높이를 초기화해주면 된다.

 

 

코드

C++

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        const int n = matrix[0].size();
        int answer = 0;

        vector<int> height(n, 0);

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) height[j] = 0;
                else height[j]++;
            }
            vector<int> ordered_height = height;
            sort(ordered_height.begin(), ordered_height.end());

            for(int j = 0; j < n; j++) {
                answer = max(answer, ordered_height[j] * (n-j));
            }
        }

        return answer;
    }
};