[Greedy]Leetcode 1727, Largest Submatrix With Rearrangements

 

 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 

 

1) Matrix의 크기가 $10^5$ 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 

2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다.

3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 

 

 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을 경우의 누적 계수를 구해준다. 0이라면 0이 되고, 위에서 부터 1이 연속되면 하나씩 더해주는 식이다. 즉, 위에서 부터 아래로 1이 몇개 연속되어 있는지를 구해놓는 것이다. 그리고 나서 decresing order로 sorting 해준다. column방향으로 정보가 섞이게 되어 이렇게 하면 안될 것 같은 생각이 든다. 하지만, 이미 이전에 column 방향으로 누적계수를 구해 놓았기 때문에 row 간에 연결 관계는 끊어진 상태다. 이게 무슨 소리일까? 변형된 matrix의 값 matrix[i][j]는 column 방향 연속 1의 개수를 포함하는 value라고만 생각하자. 그리고 decresing order로 row by row 정렬했기 때문에 다음과 같이 생각이 가능해 진다. 현재 matrix[i][j]가 0 이상이라고 한다면 (j+1, 0-index)만큼 1이 있다는 이야기고, matrix[i][j]만큼 위 아래로 연결되어 있다는 뜻이다. 즉 계산이 j * matrix[i][j]가 된다는 이야기다. (여기서 i는 row, j는 column)이다. 이해가 가지 않는다면 이 글과 아래의 예시를 주의깊게 살펴 보기 바란다. 

 

 

이게 이해 된다면,  구현은 생각보다 쉽게 아래와 같이 구현이 가능하다. Greedy는 접근 방식을 이해하고 나면 아주 재미있는 문제가 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

// F60, fail
// 각 Row를 분리하여 판단하되, column은 변하지 않기 때문에 연속되는 누적합을 계산한 후
// 각 Row 별로 최대 크기를 판별한다. reverse_sorting을 통해서 유추 가능

int largestSubmatrix(vector<vector<int>>& matrix) {
    int m = size(matrix);
    int n = size(matrix[0]);
    // column 방향으로 최대 연속 index 정리
    for(int i=0; i<n; ++i) for(int j=1; j<m; ++j) if(matrix[j][i]==1) matrix[j][i] = matrix[j-1][i] + 1;
    int ans = 0;
    for(int i=0; i<m; ++i) {
        sort(begin(matrix[i]), end(matrix[i]));
        reverse(begin(matrix[i]), end(matrix[i]));
        for(int j=0; j<n; ++j) {
            ans = max(ans, matrix[i][j]*(j+1));
        }
    } 
    return ans;
}
int main() {
    fastio;
    vvi matrix = {{0,0,1},{1,1,1},{1,0,1}};
    largestSubmatrix(matrix);
    return 0;
}