백준 오아시스 재결합(3015) C++ 풀이

알고리즘 분류

자료 구조

스택

문제 해결 아이디어

Person이라는 구조체를 만들어 높이와 자신과 같은 높이의 개수를 저장 할 수 있도록 하고, stack을 이용하고

stack이 비워있지 않고 현재 입력된 값이 top()보다 크면 볼 수 있기 때문에 더해주고, 같으면 euql에도 +하여

누적하여 더 할 수 있도록 한다.

코드

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


struct Person
{
	long height;
	long equal;
};

stack<Person> st;
long n;
long result = 0;
int main()
{
	cin >> n;

	long num;
	for (int i = 0; i < n; i++)
	{
		cin >> num;

		long cnt = 0;
		long equal = 0;

		while (!st.empty())
		{
			if (num > st.top().height)
			{
				cnt += st.top().equal + 1;
				st.pop();
			}
			else if (num == st.top().height)
			{
				cnt += st.top().equal + 1;
				equal += st.top().equal + 1;
				st.pop();
			}
			else break;
		}
		if (!st.empty()) cnt++;
		st.push({num, equal});

		result += cnt;
	}

	cout << result;
}