백준 3015번 오아시스 재결합

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

3015번: 오아시스 재결합

스택에 어떤 사람의 키와 키가 그 사람 이상이면 볼 수 있는 사람들의 수를 저장해 둔다.

그리고 그 사람이 볼 수 있는 사람들은 그 사람을 보는 다른 사람들도 볼 수 있으니 수만 세고 스택에서 제거 한다.

 

#include <iostream>
#include <algorithm>
#include<vector>
#include<stack>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, height;
	long long int sum = 0;
	cin >> N;
//pair의 first가 키, second가 볼 수 있는 사람의 수
	stack<pair<int, int>> sta;
	for (int i = 0; i < N; i++){
		cin >> height;
//더이상 볼 수 있는 사람이 없을때까지 사람들을 제거
		while (!sta.empty() && sta.top().first < height){
			sum += sta.top().second;
			sta.pop();
		}
//입력받은 사람을 스택에 추가
		if (!sta.empty() && sta.top().first == height){
			sum += sta.top().second;
			int tmp = sta.top().second + 1;
			sta.pop();
			if (sta.size()) sum++;
			sta.push({ height, tmp });
		}
		else{
			if (sta.size()) sum++;
			sta.push({ height, 1 });
		}
	}

	cout << sum;

	return 0;
}