[BOJ/3015] 오아시스 재결합 (C++)

개요

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

3015번: 오아시스 재결합

P5  자력솔 !

본문

힌트

1. 스택을 활용
2. 같은 키가 연속으로 push되는 경우를 고려

풀이

• 스택 자료구조를 활용하여 입력을 받음과 동시에 top과 비교하여 처리
  (선행 문제 : BOJ 2493번 탑)
• top이 더 클 경우 : result += (pop한 개수 + 1)개 후 push(키, 1(연속 1회를 의미))
• top과 같을 경우 : result += (pop한 개수 + 연속된 횟수) 후 push(키, 연속된 횟수)
• top이 더 작을 경우 : pop한 개수 += 1 후 pop()

코드

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

stack <pair<ll, int>> s;
ll result;
ll sumNum;
int main(){
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;

	ll h;
	for(int i=0; i<n; i++){
		sumNum = 0;
		cin >> h;
		while(true)
		{
			if(s.empty())
			{
				result += sumNum;
				s.push({h, 1});
				break;
			}
			else if(s.top().first > h)
			{
				result += sumNum + 1;
				s.push({h, 2});
				break;
			}
			else if(s.top().first == h)
			{
				result += sumNum + s.top().second;
				s.push({h, s.top().second + 1});
				break;
			}
			else
			{
				sumNum++;
				s.pop();
			}
		}
	}
	cout << result;
}