[알고리즘] 백준 1725 히스토그램 // 스택

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

* 풀이

히스토그램 문제를 직관적으로 이해하는 방법은 이렇습니다:

1. "뻗어나가기" 관점:
   • 각 막대는 자신의 높이를 유지하면서 양옆으로 최대한 뻗어나가려고 합니다
   • 예를 들어 높이 4인 막대는 "높이 4를 유지하면서 얼마나 넓은 직사각형을 만들 수 있을까?"를 생각하는 것입니다
2. "막히는 지점" 찾기:
   • 뻗어나가다가 자신보다 낮은 높이를 만나면 거기서 멈춰야 합니다
   • 이것이 바로 우리가 스택에서 pop을 하는 시점입니다
3. 스택의 역할:
   • 스택은 "아직 더 뻗어나갈 수 있는 막대들"의 모음입니다
   • 새로운 막대를 만났을 때, 이 막대보다 높은 것들은 더 이상 뻗어나갈 수 없으므로 pop하고 계산합니다

이렇게 생각하면 너비 계산도 이해하기 쉽습니다:

• 스택이 비었다는 것은 "왼쪽으로 끝까지 갈 수 있다"는 의미입니다
• 스택에 남아있는 막대가 있다면, 거기까지만 갈 수 있다는 의미입니다

• stack : 뻗어나갈수 있는 것들의 모음
• top =< cur -> 뻗어나갈수있음, push
• while(top > cur) -> 뻗어나갈수없음, 하나씩 pop 해보면서 뻗어나갈수 있었던 넓이들을 계산해야함!
  • 각각의 높이에대해 뻗어나갈수 있는지 계산

1. while(top > cur)의 의미:
   • "앗, 더 작은 높이가 나왔다!"
   • "이제 스택에 있는 큰 막대들은 더 이상 뻗어나갈 수 없겠네"
   • "여기서 이전까지의 기록들을 정산해야겠다"
2. 넓이를 계산하는 과정:
   • 스택에서 pop을 하면서 각각의 높이에 대해
   • "이 높이로는 여기까지가 한계였어"라고 판단하고
   • 그때까지 뻗어나갈 수 있었던 최대 범위를 계산합니다
3. 이 과정이 효율적인 이유:
   • 각 막대는 스택에 한 번 들어갔다가
   • 더 이상 뻗어나갈 수 없을 때 한 번 나오면서
   • 자신의 최대 넓이를 계산하게 됩니다

이 알고리즘의 아름다움은 바로 여기에 있습니다. 우리가 각 막대에 대해 "얼마나 뻗어나갈 수 있을까?"를 일일이 계산하지 않고, 스택을 사용해서 "더 이상 뻗어나갈 수 없는 시점"에 한꺼번에 계산할 수 있다는 것이죠.

 

* 넓이계산

• 높이 = stack.top, pop # top이 이제 이전의 index를 가리키도록
• 너비 = 현재 index - top.index - 1 
  • 이때 top은 이전의 index를 가리킨다.
  • 높이4인경우) 4의 우측은 항상 4보다크다 -> 4높이로 뻗어나갈수있다 -> 너비를 +1 

높이4인경우) 4의 우측은 항상 4보다크다 -> 4높이로 뻗어나갈수있다 -> 너비를 +1 이때, 너비는 4 - 1 - 1 로 계산될수있다.

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문을 탈출합니다.

 

• 즉, cur이 top보다 작은경우 -> 좌측으로 높이하나씩 탐색 -> 확장될수있었던 넓이들을 전부 계산 하면된다!
• 오름차순 stack의 특성상, 너비계산이 매우 쉬워지는것이다.

// 넓이 계산: 현재 높이로 확장 가능한 구간의 넓이
// i: 현재 위치 (더 이상 확장할 수 없는 지점)
// s.top(): 이전 막대의 위치 (확장 가능한 왼쪽 끝 지점)
// h[check]: 현재 계산하는 높이

 

* 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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;
	
}