백준 2493번 탑 C++

출처 : https://www.acmicpc.net/problem/2493

스택 자료구조를 사용하여 해결할 수 있는 문제이다. 문제를 풀고 다른 사람들의 풀이법을 보니 많은 사람들이 스택을 쌓으면서 답을 구해서 문제를 해결하였다. 나의 풀이법은 스택을 전부 쌓은 뒤에 제거해나가면서 문제를 해결하는 방법이다.

 

스택을 쌓으면서 문제를 해결하는 방법이 훨씬 간단하고 효율적인 방법인 것 같다. 접근을 잘못해서 풀이가 복잡하고 푸는데 오랜 시간이 걸린 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

struct compare {
	bool operator()(pair<int, int> lhs, pair<int, int> rhs) {
		return lhs.first > rhs.first;
	}
};

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

	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
	stack<pair<int, int>> st;
	int n, input;
	cin >> n;
	vector<int> ans(n, 0);
	for (int i = 1; i <= n; i++) {
		cin >> input;
		st.push({ input,i });
	}
	int cnt = 0;
	int maxval = 0;
	
	while (!st.empty()) {
		auto a = st.top();
		if (!pq.empty()) {
			if (a.first >= maxval) {
				while (!pq.empty()) {
					ans[pq.top().second - 1] = a.second;
					pq.pop();
				}
				pq.push(a);
				maxval = a.first;
			}
			else {
				while (true) {
					if (a.first >= pq.top().first) {
						ans[pq.top().second - 1] = a.second;
						pq.pop();
					}
					else {
						break;
					}
				}
				pq.push(a);
			}
		}
		else {
			maxval = a.first;
			pq.push(a);
		}
		st.pop();
	}
	for (auto a : ans) {
		cout << a << " ";
	}
};