3015번

3015번 - 오아시스 재결합

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-3015

https://blog.naver.com/malmstee/220990386293

↑↑↑ 문제를 푸는데 참고한 설명들...

이 문제 푸는데 정말 오랜시간이 걸렸다...

우선 핵심은 뒤에서 앞을 본다는 방식으로 생각해야 한다는 점이었다. 그리고 이 문제에서 가장 핵심은

stack에 같은 키를 가진 사람이 연속으로 서있을 때이다.

나는 이를 map 을 이용해서 구현하였다.. 같은 키를 가진 사람이 연속으로 몇명이 세워져있는지를 

cnt[ 키 ] = 몇명  으로 계산하였고, 중간에 더 큰놈이 서 있는 경우는 다시 초기화해주었다..

나중에 시간이 지나서 다시 풀어도 그때 또 어렵게 풀 것 같다... 와 이해하고 스스로 푸는데 정말 오래걸렸다..

<정답 코드>

#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
 
int main()
{
    int N;
    long long ans = 0;
    vector<int> h;
    stack<int> st;
    map<long long,long long> cnt;
    
    cin >> N;
 
    h.resize(N);
    
 
    for (int i = 0; i < N; i++)
    {
        cin >> h[i];
    }
 
    for (int i = 0; i < N; i++)
    {
        while (!st.empty())
        {
            if (h[i] >= h[st.top()])
            {
                // 스택에 처음 들어 올때 ( 아예 처음 or 연속이 끊겨서 다시 스택에 쌓일 때
                if (cnt.count(h[st.top()])==0 || cnt[h[st.top()]]==0)
                {
                    cnt[h[st.top()]] = 1;
                }
                
                //처음이면 1을, 연속이면 연속된 갯수를 더해준다.
                ans += cnt[h[st.top()]];
                
                //연속이면 기존 값에 ++
                if (h[i] == h[st.top()])
                {
                    cnt[h[st.top()]]++;
                }
                // 연속이 끊겼을 때
                else
                {
                    cnt[h[st.top()]] = 0;
                }
                
                st.pop();
                
            }
            else
            {
                break;
            }
        }
 
        if (!st.empty())
        {
            ans += 1;
        }
 
        st.push(i);
    }
 
 
    cout << ans << endl;
    return 0;
}