[개쉬운 풀이] 백준 1725 히스토그램 CPP (15일차)

문제

 

생각

Stack 방식으로 다음 오는 막대 그래프를 저장하면 된다.

Stack에는 오름차순으로만 저장이 된다. 왜냐하면 현재 최대 높이가 5 일때 그보다 작은 것이 오면 높이 5에 해당하는 사각형 넓이를 한번만 비교하면 되기 때문이다. 

이때 5에 해당하는 크기를 비교하고 삭제하는 것이 아닌 높이 5는 그 밑 숫자들이 사각형을 이룰 때 사용이 될 수 있으므로, Stack에서는 제외될 수 있어도 카운팅을 통해 저장한다.

 

1. Stack에 현재 높이와 그 높이에 해당하는 사각형 갯수들을 저장한다.

2. 최고 높이보다 큰 사각형이 오면 Stack에 저장한다.

3. Stack에 담긴 막대들은 오름차순으로 되어있기 때문에, 뒤에 있는 작은 막대들은 앞의 큰 막대들 갯수에 영향을 받는다.

 

풀이

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct T {
    ll height, cnt;

    T(int h, int c) : height(h), cnt(c) {};
};

const int MAX = 100001;
int N;
vector<ll> v;
vector<T> stack;

void input(){
    cin >> N;
    for(int i = 0; i < N; i++){
        ll tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void print(){
    for(int i = 0; i < stack.size(); i++){
        cout << stack[i].height << "("<< stack[i].cnt << ") ";
    }
    cout<<endl;
}

void sol(){
    
    stack.push_back(T(v[0], 1));
    ll answer = 0;
    //print();
    for(int i = 1; i < N; i++){

        int cur = v[i];

        if(stack.back().height < cur){
            stack.push_back(T(cur, 1));
        }
        else{
            int count = 0;
            while(true){
                T tmp = stack.back();
                stack.pop_back();
                
                if(cur == tmp.height){
                    tmp.cnt += count;
                    tmp.cnt++; //새롭게 추가된 막대 갯수 = 1
                    stack.push_back(tmp);
                    break;
                }
                //새롭게 추가된 막대가 더 큰 높이 이므로 새롭게 추가된 막대에게 count를 부여한다.
                else if(cur > tmp.height){
                    stack.push_back(tmp); 
                    stack.push_back(T(cur, count+1));
                    break;
                }
                else{ //
                    answer = max(answer, tmp.height * (tmp.cnt + count));
                    count += tmp.cnt; // 사용된 막대들 갯수
                }

                if(stack.empty()){
                    stack.push_back(T(cur, count+1));
                    break;
                }
            }
        }
        //print();
    }
    int count = 0;
    //stack 안 계산 
    while(!stack.empty()){
        T tmp = stack.back();
        stack.pop_back();

        answer = max(answer, tmp.height * (tmp.cnt + count));
        count += tmp.cnt;
    }

    cout << answer << endl;
}

int main(){
    input();
    sol();
    return 0;
}