BOJ 3015 : 오아시스 재결합

• 문제 링크 : http://boj.kr/3015
• 난이도 : P5
• 태그 : 스택

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    stack<pii> _st;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;

        while(!_st.empty() && _st.top().first < input) {
            ans += _st.top().second;
            _st.pop();
        }
        if(_st.empty()) {
            _st.push({input, 1});
            continue;
        }
        if(_st.top().first == input) {
            ans += _st.top().second;
            _st.top().second++;
            if(_st.size() > 1) ans++;
        }
        else {
            _st.push({input, 1});
            ans += 1;
        }
    }
    cout << ans;

    return 0;
}

---

풀이

#2493와 비슷하지만 더 어려운 문제다.

스택을 관리하는 방법은 동일하다. 값을 내림차순으로 정렬되게 넣고 빼주면 된다.

다만 스택에 넣고 뺄 때 개수를 세주는 부분을 잘 구현해주어야 한다. 

 

스택에 넣을 때 이전의 값이 자신의 값과 동일하다면 동일한 값의 수만큼 답에 더해진다.

추가로 스택에 자신과 동일한 값만 있지 않다면 한 개의 쌍이 더 생긴다.

 

이전의 값이 자신보다 작으면 그 작은 값들의 수만큼 답에 더해진다.

이전의 값이 자신보다 크다면 한 개의 쌍이 생겨 1만큼 답에 더해진다.