[백준 1725] 히스토그램 C++

문제

백준 1725 히스토그램

1725번: 히스토그램

풀이

오름차순 Monotonic Stack을 활용했다.

 

startIdxs(n) 배열을 사용했는데, 이 배열은 i번째 value에 대해, 그보다 작은 값이 그전 원소들 중에서 언제 처음 등장하는지 인덱스를 담고 있는 배열이다. 작은 값이 없다면 0을 담고 있다.

 

예를 들어서 5 3 2 3 5에 대해

startIdxs는 idx순서대로 각각 0, 0, 0, 2, 3이 된다.

넓이를 구할 때는 특정 원소가 빠질 때, 그 원소의 startIdxs부터 입력값의 인덱스까지 뺀 값(입력값이 들어왔음에도 안 빠져있는 경우에는 최대값 : n)에다가 자신의 높이를 곱해 구하면 된다.

 

입력값이 들어왔을 때 다음과 같은 과정을 반복한다.

 

입력값이 더 크거나 같을 경우

원소를 stack에 바로 넣어준다.

 

입력값이 더 작은 경우

오름차순 Monotonic Stack을 재구성해야 한다.

먼저 top에 있는 원소를 빼고, 그 원소에 대한 넓이를 구해준다.

스택이 비게되거나 입력값이 더 커질 때까지 반복한다.

그리고 원소를 stack에 넣어준다.

 

그리고 마지막에 stack에 남아있는 원소들에 대해, 각각 넓이를 구해주면 주어진 조건의 정답을 구할 수 있다.

소스 코드

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    int answer = 0;
    // idx, value
    stack<pair<int, int>> st;
    // 넓이 계산 시 사용
    vector<int> startIdxs(n);
 
    for (int idx = 0; idx < n; ++idx)
    {
        int height = 0;
        cin >> height;
        int width = 0;
        startIdxs[idx] = idx;
 
        // 입력값이 더 작다면, 앞의 요소 꺼내야 함.
        while (!st.empty() && st.top().second >= height)
        {
            int i = st.top().first;
            int h = st.top().second;
            startIdxs[idx] = startIdxs[i];
            st.pop();
            // 꺼낼 때 넓이 계산
            width = h * (idx - startIdxs[i]);
            answer = max(answer, width);
        }
 
        st.push({ idx, height });
    }
 
    // 남아 있는 요소들에 대해서 넓이 재확인
    while (!st.empty())
    {
        int i = st.top().first;
        int h = st.top().second;
        st.pop();
        int width = h * (n - startIdxs[i]);
        answer = max(answer, width);
    }
 
    cout << answer;
 
    return 0;
}