문제 출처

1. 문제설명

  • 도시에는 N개의 빌딩이 있다.
  • 빌딩의 키는 h이다.
  • 관리자가 i번째 빌딩에 있는 경우 -자신보다 더 높거나 같은 빌딩이 있으면 그 다음 빌딩의 옥상은 보지 못한다.
  • 관리인들이 확인할 수 있는 빌딩의 총 수를 구하라.



2. 알고리즘 설계

  • 스택 문제이다.
  • 각 빌딩의 높이를 입력받을 때마다 값을 구한다.



3. 로직

  • 가장 최근 빌딩의 높이가
  • 현재 입력된 빌딩의 높이보다
  • 작거나 같으면 스택에서 빼준다.
  • 이후 현재 스택 크기를 정답에 계속해서 더해주면 된다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

	stack<ll> st;
	ll ans = 0, tmp;
	int n; 
	cin >> n;

	while (n--) {
		ll tmp;
		cin >> tmp;

		while (!st.empty() && st.top() <= tmp) 
			st.pop();

		ans += st.size();
		st.push(tmp);
	}

	cout << ans;
	return 0;
}