[BOJ] 2493번 탑 (C++)

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

2493번: 탑

 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
	int n;
	cin >> n;

	stack <pair<int, int>> s;
	int num;

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

		while (!s.empty()) {
			if (s.top().second > num) {
				cout << s.top().first << " ";
				break;
			}		
			s.pop();
		}

		if (s.empty()) {
			cout << 0 << " ";
		}
		s.push({ i + 1, num });
	}

	return 0;
}

 

높이가 더 높은 탑 중 가장 오른쪽에 있는 탑이 수신하므로 스택을 사용한다.

 

 

탑의 높이를 하나씩 입력받을 때마다 다음 과정 반복

 

1. 스택의 top에 있는 탑의 높이와 현재 탑의 높이를 비교하여

   top에 있는 탑의 높이가 더 높으면 - 해당 탑의 번호를 출력

   현재 탑의 높이가 더 높으면 - pop하고 1번 반복

2. 스택이 비어있으면(현재 탑보다 높은 탑이 없으면) 0 출력

3. 스택에 현재 탑의 번호와 높이를 쌍으로 저장