[C++] 백준 2493번 : 탑

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

2493번: 탑

---

 문제 풀이

스택으로 풀 수 있는 문제이다.

입력받은 높이를 스택에 담고 지금 입력받은 높이가 top의 높이보다 높다면 top의 idx 값을 출력해준다.

작다면 pop을 통해서 신호를 받을 수 있는 탑의 idx를 찾는다.

신호를 받은 탑은 스택에 남겨주고, 신호를 받지 못한 탑들은 필요가 없으므로 pop 해주는 것이다.

스택이 빌 때까지 신호를 받을 수 있는 탑이 없다면 0을 출력해주면 된다.

 느낀 점

처음에는 브루트 포스로 구현하고 결괏값을 스택에 담아서 표현했으나 당연히 시간 초과가 발생한다. 스택에 결괏값이 아닌 탑의 정보를 담고 있도록 구현했고 해결할 수 있었다. 

 코드

#include <iostream>
#include <stack>

using namespace std;

int n, height;
stack<pair<int, int>>s;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> height;
		while (!s.empty()) {
			if (height < s.top().second) {
				cout << s.top().first << " ";
				break;
			}
			s.pop();
		}
		if (s.empty()) {
			cout << 0 << " ";
		}
		s.push({ i + 1, height });
	}
}