[백준 2493] 탑 (C++)

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;

    long long int input;
    vector<long long int> result;
    stack<pair<int,long long int>> towers;
    stack<pair<int, long long int>> holds;

    for (int i = 0; i < n; i++) {
        cin >> input;
        pair<int, long long int> temp;
        temp.first = i;
        temp.second = input;
        towers.push(temp);
        result.push_back(0);
    }

    while (!towers.empty()) {
        holds.push(towers.top());
        towers.pop();

        while (!holds.empty() && !towers.empty() && holds.top().second < towers.top().second) {
            result[holds.top().first] = towers.top().first + 1;
            holds.pop();
        }    
    }

    while (!holds.empty()) {
        holds.pop();
    }

    for (int i = 0; i < n; i++) {
        cout << result[i] << " ";
    }

    return 0;
}

탑을 차례로 저장하는 towers와 임시로 건물들을 저장할 holds라는 스택을 2개 활용하였다.
또 이 스택들에 건물의 인덱스를 first로, 건물의 높이를 second로 두는 pair 구조를 저장해서 인덱스를 알아내기 쉽게 만들었다.

이 문제의 경우엔 타워의 왼쪽으로 레이저를 발사한다. 따라서 마지막 타워가 제일 먼저 계산되도록 towers스택에 저장하고 pop을 해가며 크기를 비교해가도록 설계하였으며, holds스택에는 현재 순회중인 타워를 계속 쌓아둔다. holds스택에는 여러 값들이 저장될 수 있는데 이는 현재 타워가 쏜 레이저가 닿지 않는 작은 타워들을 의미하는 것이다. 모든 반복문이 종료되었음에도 holds에 데이터가 남아있다면 그 값들은 삭제한다(사실 이 과정은 지금 생각하면 전혀 필요가 없다).