[백준 c++] 3015 오아시스 재결합

문제 설명

https://www.acmicpc.net/problem/3015
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.

출력
서로 볼 수 있는 쌍의 수를 출력한다.

아이디어

같은 키를 가진 사람이 존재하기 때문에 단순히 스택으로 풀 수 없었고 pair를 담는 stack으로 풀어야 했다. 스택에는 비교할 여지가 남아있는 사람들을 넣어두고 더이상 비교할 필요가 없으면 pop을 한다.

now: now, s.top().first: 스택 탑
s.first: 키, s.second: 볼 수 있는 앞사람 수
res: 쌍의 수

크게 3가지의 경우로 나눈다.

1. now > s.top().first
   탑은 now의 뒷사람을 볼 수 없다.
   즉, 더이상 비교할 여지가 없기 때문에

	while (!s.empty() && s.top().first < now)
    		s.pop(), res++

2. now < s.top().first
   now는 탑의 앞 사람을 볼 수 없다.
   하지만 뒷사람과 비교할 여지가 있으니 s.push({now,1}) res++

3. now == s.top().first
   3 2 2 같은 경우 볼 수 있는 앞 사람 수가 각각 0,1,2다.
   즉 s.push({now, s.top().second +1}) res+=s.top().second +1

전체 코드

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
ll n, ret, now, cnt;
stack<pair<ll, ll>> s;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> now;
        if (s.empty())
        {
            s.push({now, 0});
            continue;
        }

        if (s.top().first < now) // pop진행
        {
            while (!s.empty() && s.top().first < now)
            { // top이 now보다 크거나 같아지면 끝남
                ret++;
                s.pop();
                if (s.empty())
                    break;
            }
        }

        if (!s.empty() && s.top().first == now)
        {
            cnt = s.top().second + 1;
            s.push({now, cnt});
            ret += cnt;
            continue;
        }

        if (!s.empty() && s.top().first > now)
        {
            ret++;
            s.push({now, 1});
            continue;
        }
        s.push({now, 0});
    }
    cout << ret << "\n";
}