문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

• 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

• 첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

---

1. 기본 아이디어 및 소스코드

• 스택을 활용하여 해결한다.

• 히스토그램 배열은 모두 0으로 초기화 되어있으며, 인덱스 [1]부터 [N]까지 높이들을 입력받는다.

• 입력받은 배열에서 for loop을 돌며 중간중간 답을 구한다.

  1. hgram[i-1] <= hgram[i]이면 스택에 i를 쌓는다. (즉, 스택에는 직접 높이값을 저장하는 것이 아니라 히스토그램 배열의 인덱스를 저장)
  2. 만약, i번째 높이가 i-1번째 높이보다 낮다면, 일단 흐름이 끊겼다고 볼 수 있으므로, 여태까지 나온 직사각형들에서 최대넓이를 구하는 과정을 들어간다.

• 위의 2번에서 실행하는 현재까지 나온 직사각형들에서 최대넓이를 구하는 과정은 다음과 같다.

  1. check 변수에 현재 스택의 top을 저장해둔다. (넓이를 구할 직사각형의 높이를 가지고 있는 인덱스를 저장)
  2. 맨 위를 pop한다.
  3. C++의 max함수를 이용하여 현재까지 구해놓은 최댓값과 지금 구한 직사각형의 넓이와 비교하여 최댓값을 업데이트한다. 직사각형의 넓이는 hgram[check] * (i - s.top() - 1)로 구할 수 있다.

• 자세한 아이디어는 https://cocoon1787.tistory.com/315 포스트의 그림을 참고하여 이해 가능하다.

#include <iostream> #include <stack> #include <algorithm> using namespace std; int main() { int N, ans = 0; int hgram[100005] = { 0, }; stack<int> s; //스택이 비어서 오류 나는 경우 방지 s.push(0); scanf("%d", &N); //히스토그램 채우기 (인덱스는 1부터) for (int i = 1; i <= N; i++) scanf("%d", &hgram[i]); //해답 구하는 과정 for (int i = 1; i <= N + 1; i++) { //스택의 맨 위의 인덱스에 해당하는 높이보다 현재 높이가 낮으면 계속 pop한다. while (!s.empty() && hgram[i] < hgram[s.top()]) { int check = s.top(); s.pop(); ans = max(ans, hgram[check] * (i - s.top() - 1)); } s.push(i); } printf("%d\n", ans); }