[백준/BOJ] 3321 가장 큰 직사각형

문제 : 3321 가장 큰 직사각형

3321번: 가장 큰 직사각형

기본적으로 1로 채워진 가장 큰 정사각형을 찾는 문제이지만

열의 순서를 바꿀 수 있으므로 결국 각 행에 대해서 열의 높이를 정렬하여 누적합을 이용하면

행의 길이를 1씩 늘려가면서 최대 넓이를 구할 수 있다.

이를 구현하게 되면 총 행의 개수 N번, 각 행을 정렬하는데 걸리는 시간이 퀵 정렬 사용 시 MlogM이므로

시간 복잡도가 O(NMlogM)이 되는데 시간제한이 0.6초이기 때문에 이를 O(NM)으로 줄여야 한다.

 

나 같은 경우에는 deque를 사용해 정렬 시간을 O(2M)으로 줄였는데

현재 높이와 인덱스를 pair로 묶어 deque에 저장하고 시작하면

그 이후에서는 현재 높이+1이 되거나 0이 되거나 두 경우중 하나이므로

이를 새로운 두 덱으로 쪼갰다가 합치는 방법으로 구현하게 되면 2번 순회하는 것으로 정렬이 가능하다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> pll;
ll N, M, ans;
deque<pll> dq, dq1, dq2;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<M;i++)
        dq.push_back({0,i});
    for (int i=0;i<N;i++){
        string s;
        cin >> s;
        while (!dq.empty()){
            ll len=dq.front().first, idx=dq.front().second;
            dq.pop_front();
            if (s[idx]=='1')
                dq1.push_back({len+1, idx});
            else
                dq2.push_back({0, idx});
        }
        while (!dq1.empty()){
            dq.push_back(dq1.front());
            dq1.pop_front();
        }
        while (!dq2.empty()){
            dq.push_back(dq2.front());
            dq2.pop_front();
        }
        for (int j=0;j<M;j++)
            ans=max(ans,(j+1)*dq[j].first);
    }
    cout << ans;
    return 0;
}