[백준 C++] 6549번 히스토그램에서 가장 큰 직사각형(스택, 라인 스위핑)

히스토그램에서 가장 큰 직사각형

기록을 확인 해보니 정확하게 23일 전에 분할정복으로 해결하려고 했다가 시간초과 문제를 도저히 해결할 수 없어서 포기했던 문제다. 풀지 못했던 문제를 시간이 지남에 따라 풀 수 있게 되는 것도 알고리즘 공부의 쏠쏠한 재미인 듯 하다.

히스토그램에서 '가장 큰 직사각형'이 되기 위해서는 각 높이(height)를 가지고 만들 수 있는 가장 큰 직사각형 중 가장 큰 값이어야 한다. 각 막대는 자신보다 작거나 같은 최초의 막대를 왼쪽과 오른쪽에서 각각 하나씩 찾아야 한다. 왼쪽과 오른쪽 값을 찾는 것이 이 문제의 시간 복잡도를 결정짓는다.

나도 처음에 생각했던 Brute Force로 한다고 하자. 최악의 경우에 각 막대는 가장 왼쪽까지, 그리고 가장 오른쪽까지 탐색해야 결과를 얻을 수 있다. 그러므로 시간복잡도는O($N^2$)이다. 1초 안으로 풀어야 하는데 입력값으로 주어진 막대의 최대 갯수는 100,000개인데 처리하기 힘들 것으로 보였다.

이 문제의 경우 탐색 시간을 줄이기 위해 라인 스위핑(Line Sweeping)이라고 한다. Brute Force 기법에서는 막대를 기준으로 왼쪽과 오른쪽을 탐색했다면, 라인 스위핑 기법을 사용하면 오른쪽으로만 탐색하면 된다. 왼쪽 값의 경우에는 시작점부터 탐색하면 자연스럽게 알 수 있다. 이런 식으로 시작점으로부터 오른쪽으로 훑으면서(sweep) 문제 해결에 필요한 연산을 동시에 진행해 한번에 마치는 것을 라인 스위핑이라 한다.

어떻게 이것이 가능한지는 아래 코드의 21 - 30 번째 줄을 보면 알 수 있다. 간단하게 설명하자면 stack에는 height가 들어가며, 앞선 height가 현재 height보다 크거나 같다면 넓이를 구하고, stack에서 하나를 뺀다. 이렇게 하면 어떤 경우에도 stack에는 현재 막대보다 큰 것은 없다. 이렇게 만들어 주면 좋은 점이 stack.top()을 조회하기만 해도 왼쪽 값의 index를 알 수 있다. 별도의 탐색이 필요없는 것이다. 

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
#define FOR(i, N) for (int i = 1; i <= N; i++)
#define MAX(a, b) a > b ? a : b
#define ll long long
ll hgt[100000 + 2];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  int N;
  while (1) {
    cin >> N;
    if (N == 0) break;
    ll max = 0;
    memset(hgt, 0, sizeof(hgt));
    stack<ll> st;
    FOR(i, N) cin >> hgt[i];
    st.push(0);
    FOR(i, N + 1) {
      if (hgt[i - 1] >= hgt[i]) {
        while (!st.empty() && hgt[st.top()] >= hgt[i]) {
          ll tmpHgt = hgt[st.top()];
          st.pop();
          if (!st.empty()) max = MAX(max, tmpHgt * (i - st.top() -  1));
        }
      }
      st.push(i);
    }
    cout << max << '\n';
  }
}