백준 3015 오아시스 재결합(c++)

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

3015번: 오아시스 재결합

이 문제는 N명이 한 줄로 서있을 때 서로 마주칠 수 있는 쌍의 수를 구하는 문제입니다. 비교적 어려운 문제는 아니지만, 키가 같은 경우 때문에 고려사항이 많은 문제입니다. 

테스트 케이스로 설명 드리겠습니다.

case 1 :

7
2
4
1
2
2
5
1

다음과 같이 키가 2 4 1 2 2 5 1 일 경우에는 서로 마주할 수 있는 쌍은 (1 2), (2,3), (2,4), (2,5), (2,6), (3,4), (4,5), (4,6), (5,6), (6,7)

입니다. 왜냐하면, A, B가 마주하기 위해서는 A 또는 B보다 큰 키를 가진 사람이 없어야 하기 때문입니다.

앞사람 보다 뒷사람의 키가 크거나 같다면, 개수를 하나 늘려주고 그중에서도 키가 같은 경우가 존재한다면, 인원수를 하나 증가시켜 줍니다.

 

<코드>

#include <iostream>
#include <stack>

using namespace std;

int height[500001];

int main()
{
    int n;
    cin >> n;
    stack<pair<int, int>> s;
    for (int i = 0; i < n; i++)
    {
        cin >> height[i];
    }
    long long ans = 0;

    for (int i = 0; i < n; i++)
    {
        pair<int, int> p = {height[i], 1};
        while (!s.empty())
        {
            if (s.top().first <= height[i])
            {
                ans += (long long)s.top().second;
                if (s.top().first == height[i])
                {
                    p.second += s.top().second;
                }
                s.pop();
            }
            else
            {
                break;
            }
        }
        if (!s.empty())
            ans += 1LL;
        s.push(p);
    }

    cout << ans << '\n';
}