[백준] 1725번: 히스토그램

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

1725번: 히스토그램

스택 연습문제
어처구니 없는 실수로 시간을 많이 잡아먹은 문제이다.

스택의 top 보다 높이가 높은 경우에만 스택에 push하고
(이렇게 되면 스택은 무조건 top으로 갈수록 높이가 높은 막대들만 쌓이게 된다)

top보다 높이가 낮거나 같은 막대가 나왔을 때에는
현재 막대가 스택의 top 보다 높이가 높아질 때까지 스택을 pop한 뒤,
pop한 막대의 높이로 구할 수 있는 최대 넓이를 구해준다.
이 값이 현재 저장되어 있는 result 값보다 큰 경우에만 result에 넣어주면 끝!

정리하자면,

1. 현재 막대 높이가 top 보다 높은 경우 => 스택에 push

2. 현재 막대 높이가 top보다 낮거나 같은 경우

   => 스택에서 현재 막대 높이보다 높거나 같은 막대를 모두 pop한 후, 각각의 높이에서의 최대 넓이 계산
   i) pop한 후에 스택에 원소가 남았을 때: pop한 막대 높이 * (현재 위치 - 남아있는 스택의 top -1)
   ii) pop한 후에 스택이 비었을 때: pop한 막대 높이 * (현재 위치 - 1)

3. 모든 막대를 탐색한 후 스택에 원소가 남았을 때
   => 스택이 빌 때까지 pop하며, 각각의 높이에서의 최대 넓이 계산
   i) pop한 후에 스택에 원소가 남았을 때: pop한 막대 높이 * (n - 남아있는 스택의 top)
   ii) pop한 후에 스택이 비었을 때: pop한 막대 높이 * n

 

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int height[100001];
	stack<int> s;
	int result = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> height[i];

	s.push(1);

	for (int i = 2; i <= n; i++) {
		// 스택의 원소 높이가 현재 원소의 높이보다 작아질 때까지 pop
		while (!s.empty() && height[i] <= height[s.top()]) {
			int top = s.top();
			s.pop();

			// pop된 원소에서의 최대 넓이 계산
			if (!s.empty()) {
				int area = height[top] * (i - s.top() - 1);
				result = max(result, area);
			}
			else {
				int area = height[top] * (i - 1);
				result = max(result, area);
			}
		}
		s.push(i);
	}

	while (!s.empty()) {
		int top = s.top();
		s.pop();

		// pop된 원소에서의 최대 넓이 계산
		if (!s.empty()) {
			int area = height[top] * (n - s.top());
			result = max(result, area);
		}
		else {
			int area = height[top] * n;
			result = max(result, area);
		}
	}

	cout << result;
}

---

처음에 스택에 높이 0짜리 원소를 넣어두면 더 깔끔하게 구현할 수 있다

 

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int height[100001];
	stack<int> s;
	int result = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> height[i];
	height[0] = 0;

	s.push(0);

	for (int i = 1; i <= n; i++) {
		// 스택의 원소 높이가 현재 원소의 높이보다 작아질 때까지 pop
		while ((s.size() > 1) && (height[i] <= height[s.top()])) {
			int top = s.top();
			s.pop();

			// pop된 원소에서의 최대 넓이 계산
			int area = height[top] * (i - s.top() - 1);
			result = max(result, area);
		}
		s.push(i);
	}

	while (s.size() > 1) {
		int top = s.top();
		s.pop();

		// pop된 원소에서의 최대 넓이 계산
		int area = height[top] * (n - s.top());
		result = max(result, area);
	}

	cout << result;
}