[Algorithm][Stack][백준] 6549 : 히스토그램에서 가장 큰 직사각형

 

문제 출처 : www.acmicpc.net/problem/6549

순서

I. 문제
II. 접근
III. 구현

---

I. 문제

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

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

입력

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

출력

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

[입력]
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

[출력]
8
4000

II. 접근

1. 왼쪽부터 오른쪽으로 탐색한다.( for문 )
2. 탐색할 때 다음 사각형의 높이가 stack.top()보다 크다면 현재idx와 h push().
3. 만약 작거나 같으면 stack.pop()하며 넓이 구한다.
4. 반복하다가 더 이상 stack.top()의 높이보다 작거나 같지 않으면 멈추고 push()
중요!!
여기서 push할 때 가장 마지막의 stack.top()의 idx와 현재 idx의 H를 넣어주어야 한다.
(그림참고)

 

그림설명

(1) (0,2) push

(2) 2 > 1 이므로 2 pop, 1 push
하지만 이때 idx = 0, h = 2로 push해준다!

(3) 1<3과 1<4이므로 2번 다 push

(4-1) 5>1 이므로 반복해서 pop

(4-2) stack.top() >= H[idx]이므로 모두 pop하고
바로 stack.idx와 현재idx의 H를 push하므로

(5) 나머지 2개 다 높기 때문에 모두 push()

(6) 스택에 남은 부분 처리

스택에 남은 부분 처리는 따로 처리할 필요 없이
마지막 블럭에 H = 0인 블럭을 추가하여 한 단계 더 진행하면 된다.

---

III. 구현

높이와, 경우의 수가 굉장히 크기 때문에 long long int 등의 큰 자료형을 사용해주어야 한다.

<hide/>
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
typedef long long int lli;

// 구조체 정의
struct stu_stk {
	lli order;
	lli h;
};

stack<stu_stk> stk; //스택
vector<lli> ansV; //정답위한 Vector

int N;
lli H[100000+10];
lli maxA;

void input()
{
	memset(H, 0, sizeof(H));
	maxA = 0;

	for (int j = 0; j < N; j++)
	{
		scanf("%lld", &H[j]);
	}
}

lli solve()
{
	lli refidx; // 가장 왼쪽 idx

	for (int i = 0; i <= N; i++)
	{
		refidx = i; 
        // 같거나 작으면 처리해줌
		while (!stk.empty() and stk.top().h >= H[i]) {
        
            // 현재 stack에 있는 idx로 변경
			refidx = stk.top().order;
            
            // 넓이 구하고 업데이트
			lli width = i - refidx;
			lli tempA = width * stk.top().h;

			if (maxA < tempA) maxA = tempA;
			stk.pop();
		}
        // 여기서 refidx와 H[i]를 넣는것이 중요함.
        // 이것으로 인해 좌측 우측 동시확인이 필요 없어짐.
        // 어차피 높이는 H[i]일 것이고 순서를 앞쪽으로 당겨서 
        // 24242 같은 예외처리를 해주는 것
		stk.push(stu_stk{ refidx, H[i] });
	}
	return maxA;
}

int main() {
	while(1)
	{
		scanf("%d", &N);
		if (N == 0) break;
		else
		{
			input();
			ansV.push_back(solve());
		}
	}

	for(int i=0; i<lli(ansV.size());i++)
	{
		printf("%lld\n", ansV[i]);
	}
	return 0;
}