3015번: 오아시스 재결합 (BOJ C/C++)

3015번: 오아시스 재결합

사용 언어: C++

 

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

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

 

풀이

한 가지만 주의할 점은 키가 같은 사람이 존재할 때의 조건도 생각을 해야 한다는 것이다. 

#include <iostream>
#include <stack>
#include <utility>
using namespace std;

int N, height;
stack<pair<int,int>> Stack;
long long ans;

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

    cin>>N;

    while(N--)
    {
        cin>>height;
        int same_height_cnt=1;
        //키가 같거나 작을 경우
        while(!Stack.empty() && Stack.top().first <= height)
        {
            ans += Stack.top().second;
            if(Stack.top().first == height)
                same_height_cnt += Stack.top().second;
            Stack.pop();
        }
        //키가 더 크지 않으면 서로 볼 수 있음
        if(!Stack.empty())
            ans++;
        Stack.push({height, same_height_cnt});
    }

    cout<<ans<<'\n';

    return 0;
}