백준 No.1725 [히스토그램]

백준 No.1725 [히스토그램]

---

  문제 

1725번: 히스토그램 (acmicpc.net)

1725번: 히스토그램

---

  설명 

 <알고리즘 분류> 
 * 스택

  스택 자료구조를 이용하여 히스토그램 그래프상에서 가장 넓은 직사각형을 구하는 문제이다. 아래 특징을 고려해야 한다.

 

[특징]

1. k 번째 값을 입력받았을 땐, k - 1 번째 값까지 다뤄진 stack 을 다룬 뒤, 마지막으로 k 번째 값을 stack에 push 한다.

    => k 번째 값은 그대로 push 되는게 아니라, stack에서 현재 k번째 값의 높이보다 큰 값이 나올 때 까지 pop 하면서 k번째 값의 index 값이 변형되어 push될 수 있다.

 

2. Stack에 있는 값 {idx, height} 는 현재까지 작업하면서 height 의 높이를 가지는 사각형은 idx 값부터 지금까지 이어져온다 라는 의미라고 생각하면 된다..!

---

[ 0 번째 값 입력 ]

  맨 첫번째 값은 별다른 작업 없이 stack에 push 된다.

---

[ 1 번째 값 입력 ]

  1 번째 값의 높이는 기존 stack의 꼭대기에 있던 값의 높이값보다 낮다. 이렇게 되면, 결국 0 번째 그래프는, 이 이후로 사각형을 만들 때 두번째 블록은 쓸 수 있는 일이 없게된다.  answer 값은 위 초록색 칠해진 영역으로 우선 2로 값이 바뀐 뒤,  기존의 Stack에 있던 꼭대기 값은 pop 되고, pop 된 값의 index 값과 1 번째 값의 높이 값을 가지는 원소가 push 된다.

---

[ 2 번째 값 입력 ]

  2 번째 값은 Stack의 꼭대기에 있던 값의 높이값 보다 더 높다. 그래서 그냥 push 한다. 왜냐면? Stack 에 이전에 뭐가 있었던, 지금 2번째 값의 높이가 더 크므로 다 커버칠 수 있기 때문이다.

---

[ 3 번째 값 입력 ]

  3 번째 값도 방금 push된 Stack의 꼭대기에 있는 값의 높이값 보다 더 높다. 그래서 이 값도 그냥 push 한다.

 

지금까지 Stack 에 저렇게 세 값이 있는데! 저 의미는 스택 아래서부터 순서대로 다음으로 높이 1짜리가 나온다? 하면 가로 길이는 index 0 까지 퍼뜨릴 수 있고, 높이 2 ~ 4 짜리가 나온다? 하면 가로 길이는 index 2 까지 퍼뜨릴 수 있고, 높이 5 짜리가 나온다? 하면 가로 길이는 index 3 까지 퍼뜨릴 수 있다는 의미이다.

---

[ 4 번째 값 입력 ]

  4 번째 값의 높이는 1이다. 그럼, 4번째 이후로 오는 값들은 1 보다 높은 높이를 가져봤자 4 번째의 저 하나짜리 블록을 마주하는 순간 높이는 1 까지 밖에 가지지 못한다. 그래서 Stack 에서 다 빼버린다. Stack 의 마지막 값 또한 높이 1을 가지고 있으므로 우선 뺀다. 이후 {마지막으로 pop 한 원소의 index 값, 현재 push 한 값의 높이값} 을 Stack 에 push 한다.

  또한, pop 을 하면서 그 pop 하는 원소들로 가질 수 있는 최대 넓이를 계산하게 된다. 그래서 위 초록색 블록들처럼 8의 값을 가지게 된다.

---

[ 5 번째 값 입력 ]

  5 번째 값의 높이는 Stack 의 꼭대기에 있던 원소의 높이보다 크므로 그냥 push 한다.

---

[ 6 번째 값 입력 ]

  6 번째 값은 방금 입력된 Stack 꼭대기에 있는 원소의 높이랑 똑같으므로, 우선 Stack 에서 pop 을 한다. 그리고 그 다음 Stack 꼭대기의 원소는 높이가 1 이므로 더이상 pop 하지말고 {마지막으로 pop한 원소의 index 값 (5), push 하는 값의 높이값} 을 push 한다.

---

[ 7 번째 값 ]

  7 번째 값은 사실 없고, 그냥 마지막으로 입력된 값인 6번째 값을 다루기 위해서 마련한 자리일 뿐이다. 

 

 <정리> 
1. 새로운 값을 처리하려 할땐? Stack 에서 현재 새로운 값의 높이 값보다 낮은 원소가 나올 때 까지 pop 해버린다. 이후 마지막으로 pop 한 원소의 index 값과 지금 입력하려던 새로운 값의 높이 값을 Stack 에 push 한다.
2. 위 1번에서 pop 을 하면서, pop 을 하는 영역 내에서 최대한 큰 넓이를 계산해보게 된다.

---

  Code 

#include <iostream>
#include <vector>
#include <stack>
#define N 111111

using namespace std;
typedef long long ll;

struct s1 {
	int idx;
	ll h;
};

int n;
int idx;
ll ans = 0;
ll arr[N];

int main() {
	cin >> n;
	stack<s1> s;

	arr[n] = 0;

	for (int i = 0; i <= n; i++) {
		if (i < n) cin >> arr[i]; // 0 ~ n-1 일땐 arr값을 입력

		idx = i;

		while (!s.empty() && s.top().h >= arr[i]) {
			idx = s.top().idx;
			ll w = ll(i) - ll(idx);
			ans = max(ans, w * s.top().h);
			s.pop();
		} 
		
		s.push({ idx, arr[i] });
	} 
	cout << ans << '\n';
}