[백준] 3015 오아시스 재결합

⚡백준 3015 오아시스 재결합

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

• 첫 번째 코드(시간 초과)

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

const int MAXN = 500000;

int n;
int height[MAXN+1] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> height[i]; 

	long long cnt = 0;
	for (int i = 0; i < n-1; ++i) {
		//인접한 쌍
		cnt++;

		int ub = n - 1;
		for (int j = i+1; j < n; j++) {
			if (height[i] < height[j]) {
				ub = j;
				break;
			}
		}
		cnt += (ub - i - 1);
	}

	cout << cnt;
	return 0;
}

풀이

• 스택 사용

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

typedef long long int ll;
const int MAXN = 500000;

int n;
int height[MAXN+1] = { 0 };
stack <pair<ll, ll>> possible;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> height[i]; 

	
	ll cnt = 0;
	for (int i = 0; i < n; i++) {
		//중복된 개수
		int same = 1;
		while (!possible.empty() && possible.top().first <= height[i]) {
			if (possible.top().first == height[i]) {
				cnt += possible.top().second;
				same = possible.top().second + 1;
				possible.pop();
			}
			else {
				cnt += possible.top().second;
				possible.pop();
				same = 1;
			}
		}

		if (!possible.empty()) cnt++;
		possible.push(make_pair( height[i], same));
	}

	cout << cnt;
	return 0;
}

📌참고자료

• 백준 3015 오아시스 재결합 풀이
  https://justicehui.github.io/coi/2018/11/06/BOJ3015/