[BOJ] 6549 - 히스토그램에서 가장 큰 직사각형

https://www.acmicpc.net/problem/6549

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

문제 유형: 히스토그램, 스택(모노토닉 스택), 세그먼트 트리, 분할 정복, 투 포인터

문제 난이도: Platinum V

시간 제한: 1초

메모리 제한: 256MB

 

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

 

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

풀이

1. 모노토닉 스택을 이용한 히스토그램

핵심은 "범위에서 가장 낮은 높이"가 가장 중요한 요인이 된다.

만약 예제 n=7, [2, 1, 4, 5, 1, 3, 3]에서,

[4, 5]를 포함하고 있어서 4*2 = 8인데, 1을 만나면 [4, 5, 1]이므로, 1 * 3 = 3이 되어서, 값이 작아진다.

즉, 이번에 추가할 막대를 추가하기 전에, 현재 막대들보다 큰 막대들을 스택에서 제거하면서 기존 스택의 톱 막대를 기준으로 구할 수 있는 직사각형들을 만들어보는 것이다.

높이는 스택의 톱 막대의 높이(스택의 톱부터 이번에 추가할 막대 이전까지의 구간의 최소 높이는 스택의 톱 높이이다.)겠고, 너비는 (이번에 넣을 막대의 인덱스 - 스택의 톱 막대의 인덱스 + 1)이다.

그렇게 만들어보면서 최대값을 갱신하고, 새로 막대를 추가해주면 된다.

 

 

2. 세그먼트 트리

세그먼트 트리를 이용하면, 특정 구간에 대한 특정 연산 결과를 빠르게 구할 수 있다.

여기서는 특정 구간에 대한 "최소값의 인덱스"를 세그먼트 트리의 노드로 저장할 것이다.

왜냐하면, 전체 구간에서 분할을 해야 하는데, 가장 높이가 낮은 곳을 기준으로 그 부분의 전후로 분기하면, 최소 높이가 커질 것이기 때문이다.

그래서, 최소값의 인덱스를 쿼리가 리턴하도록 세그먼트 트리를 구성해야 한다.

그래서, 현재 구간에 대해서 최대 넓이를 알려면, 우선 구간 전체에 대한 통짜 직사각형 크기를 구하고,

가장 높이가 낮은 막대 이전의 사이드, 가장 높이가 낮은 막대 이후의 사이드 두 부분을 재귀적으로 구해서, 가장 큰 직사각형 크기들의 후보를 가져올 수 있다.

최종적으로 (현재 구간 전체에서 구하기, 왼쪽 사이드, 오른쪽 사이드) 중에서 가장 큰 크기를 반환하면 된다.

 

 

코드

C++(모노토닉 스택을 이용한 히스토그램)

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  while ((cin >> n) && n != 0) {
    vector<int> hist(n);
    for (int i = 0; i < n; ++i) {
      cin >> hist[i];
    }

    ll ans = 0;
    stack<int> stk;
    for (int i = 0; i <= n; ++i) {
      while (!stk.empty() && (i == n || hist[i] < hist[stk.top()])) {
        int h = hist[stk.top()];
        stk.pop();
        int w = stk.empty() ? i : i - stk.top() - 1;
        ans = max(ans, (ll)h * w);
      }
      stk.push(i);
    }
    cout << ans << "\n";
  }
  return 0;
}

 

Go(세그먼트 트리)

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	arr []int32
	seg []int32
)

func build(index, l, r int32) {
	if l == r {
		seg[index] = l
		return
	}

	mid := (l + r) / 2
	build(index*2, l, mid)
	build(index*2+1, mid+1, r)
	if arr[seg[index*2]] < arr[seg[index*2+1]] {
		seg[index] = seg[index*2]
	} else {
		seg[index] = seg[index*2+1]
	}
}

func query(index, ql, qr, l, r int32) int32 {
	if ql > r || qr < l {
		return -1
	}
	if ql <= l && r <= qr {
		return seg[index]
	}

	mid := (l + r) / 2
	lq := query(index*2, ql, qr, l, mid)
	rq := query(index*2+1, ql, qr, mid+1, r)
	if lq == -1 && rq == -1 {
		return -1
	}
	if lq == -1 {
		return rq
	}
	if rq == -1 {
		return lq
	}
	if arr[lq] < arr[rq] {
		return lq
	}
	return rq
}

func solve(l, r, n int32) int64 {
	if l > r {
		return 0
	}
	minIdx := query(1, l, r, 1, n)

	currRange := int64(arr[minIdx]) * int64(r-l+1)
	leftRange := solve(l, minIdx-1, n)
	rightRange := solve(minIdx+1, r, n)

	if currRange >= leftRange && currRange >= rightRange {
		return currRange
	} else if leftRange >= currRange && leftRange >= rightRange {
		return leftRange
	} else {
		return rightRange
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	arr = make([]int32, 100001)
	seg = make([]int32, 400004)
	for {
		_, err := fmt.Fscan(reader, &n)
		if err != nil || n == 0 {
			break
		}
		for i := int32(1); i <= n; i++ {
			fmt.Fscan(reader, &arr[i])
		}
		build(1, 1, n)

		fmt.Fprintln(writer, solve(1, n, n))
	}
}