[C/C++] 백준 1725번 - 히스토그램 (스택 풀이)

문제

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

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

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

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

입력

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

출력

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

 

<코드>

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;

int N, ans, h[100002];
stack<int> s;

int main() 
{
	cin >> N;

	for (int i = 1; i <= N; i++) cin >> h[i];

	s.push(0);
	for (int i = 1; i <= N + 1; i++)
	{

		while (!s.empty() && h[s.top()] > h[i])
		{
			int check = s.top();
			s.pop();
			ans = max(ans, h[check]*(i - s.top() - 1));
		}
		s.push(i);
	}
	cout << ans;
	
}

 

 

1725번 히스토그램 문제와 6549번 히스토그램에서 가장 큰 직사각형 문제는 출력 형식만 다른 동일한 문제입니다.

1725번: 히스토그램

 

둘 다 스택 혹은 분할 정복으로 풀이할 수 있는데 분할 정복 및 세그먼트 트리 방법의 풀이법이 궁금하신분은 아래의 링크를 참고해주세요!

cocoon1787.tistory.com/314

[C/C++] 백준 6549번 - 히스토그램에서 가장 큰 직사각형 (분할 정복, 세그먼트 트리 풀이)

 

 

풀이 방법

문제 풀이의 핵심은 막대의 인덱스를 순서대로 스택에 push 할 때 push 하려는 막대의 높이가 스택의 top 인덱스의 막대 높이보다 크거나 같다면 계속해서 스택을 쌓습니다. 그러다가 push하려는push 하려는 막대의 높이가 스택의 top 인덱스의 막대 높이보다 작을 경우 스택의 top 인덱스의 막대 높이가 push 하려는 막대의 높이보다 작아질 때까지 while문을 도는데, while문 안에서는 스택을 하나씩 pop 하면서 구할 수 있는 직사각형의 최대 넓이를 구하게 됩니다.

 

입력 예제 1을 예시로 시뮬레이션을 돌려보겠습니다.

s.push(0);
for (int i = 1; i <= N + 1; i++)
{

	while (!s.empty() && h[s.top()] > h[i])
	{
		int check = s.top();
        	s.pop();
		ans = max(ans, h[check]*(i - s.top() - 1));
	}
	s.push(i);
}

 

예제 입력 1의 히스토그램입니다. for문에 진입하기 전 오류 방지(스택이 비어있는 스택의 top을 확인할 경우 오류)를 위해서 스택에 0을 먼저 push 합니다.

i가 1일 때 while문에 진입하지 않고 1을 push 합니다. 스택에는 막대의 인덱스가 push 됩니다.

i가 2일 때 h[i]가 h[s.top()]보다 작으므로 2를 스택에 push 하기 전에 while문으로 진입하여 직사각형의 넓이를 구합니다.

먼저 스택의 top인 1을 check변수로 저장하고 스택을 pop 합니다. 그렇다면 스택의 top은 0이 되고 직사각형의 넓이는 h[check] * (i - s.top() - 1) = 2 * (2 - 0 - 1) = 2가 됩니다. while문이 종료된 후 스택에 i를 push 하고 다시 반복문으로 올라갑니다.

 

그리고 i는 3, 4일 때 push 하려는 막대의 높이가 스택의 top 인덱스가 가리키는 막대의 높이보다 높으므로 계속 push 해줍니다.

 

i가 5일 때 5번 막대의 높이가 스택의 top 인덱스가 가리키는 막대의 높이보다 작습니다. 따라서 while문에 진입 하게 됩니다. 먼저 스택의 top인 4를 check변수에 저장하고 스택을 pop 합니다. h[check] * (i - s.top() - 1) = 5 * (5 - 3 - 1) = 5가 됩니다. ans에는 max함수를 통해 5가 기록됩니다. 그리고 while문의 끝까지 내려왔으므로 다시 while문의 조건을 살펴보니, h[i]가 h[s.top()]보다 작으므로 다시 한 번 더 while문을 돕니다.

 

스택의 top은 3이었으므로 3을 check변수로 저장해주고 스택을 pop 합니다. pop 한 뒤 스택의 top는 2입니다. 다시 넓이를 구해보면 h[check] * (i - s.top() - 1) = 4 * (5 - 2 - 1) = 8입니다. max함수를 통해 ans는 8이 기록됩니다. 그리고 스택의 top이 2이므로 h[2] == h[5] 이기 때문에 while문을 탈출합니다.

 

while문을 탈출했으므로 스택에 i인 5를 push 해주고 다시 반복문의 위로 올라갑니다. 

 

i가 6,7일 때 h[i] >= h[s.top()] 였었으므로 while문을 진입하지 않고 계속 push 해줍니다. 스택에는 [0, 2, 5, 6, 7]이 쌓여있습니다.

 

제가 코드에서 for (int i = 1; i <= N + 1; i++)을 해준 이유가 바로 이러한 이유 때문입니다. 1~N까지 반복문을 돌게 되면 마지막에 쌓인 스택들을 계산하지 않고 코드가 종료되기 때문입니다. 여기서 h [8]의 값은 '0'입니다.(처음에 배열을 전역으로 선언하여 모든 원소가 0으로 초기화되었기 때문.) 위와 같은 방식으로 직사각형의 넓이는 3입니다.

 

이번의 직사각형의 넓이는 h[check] * (i - s.top() - 1) = 3 * (8 - 5 - 1) = 6입니다.

 

스택의 top은 5였었으므로 check변수에 5를 저장하고 스택을 pop 해줍니다.
직사각형의 넓이는 h[check] * (i - s.top() - 1) = 1 * (8 - 2 - 1) = 5입니다.

 

스택의 top은 2였었으므로 check변수에 2를 저장하고 스택을 pop 해줍니다.
직사각형의 넓이는 h[check] * (i - s.top() - 1) = 1 * (8 - 0 - 1) = 7입니다. 그리고 h[s.top()] == h[i]이므로 코드는 종료되고 정답은 8을 출력하게 됩니다.

 

 

 

 

아래의 링크는 백준 6549번 - 히스토그램에서 가장 큰 직사각형 문제의 테스트케이스인데

"백준 1725번 - 히스토그램" 과 사실상 같은 문제이기 때문에 반례케이스가 필요하시다면 참고하세요.

<대회에서 공개된 문제 TC 리스트(반례)>

www.informatik.uni-ulm.de/acm/Locals/2003/input/histogram.in

 

 

www.acmicpc.net/problem/1725

1725번: 히스토그램