[BOJ] 2493. 탑 (C++)

문제

일직선 위에 N개의 높이가 다른 탑을 세우고, 꼭대기에 송신기를 설치했다.

하나의 탑에서 신호는 왼쪽 수평 방향으로 발사하고, 가장 먼저 만나는 하나의 탑에서만 수신이 가능하다.

탑의 개수 N, 각각의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 출력

수신하는 탑이 존재하지 않으면 0을 출력

생각할 것

탑 높이를 스택에 넣으면서 자기보다 높으면 유지, 낮으면 없애기 → push, pop연산이 N번만 이루어질 수 있음

코드

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

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

    int N, h;
    cin >> N;

    stack<pair<int, int>> st; // index, height
    for (int i = 1; i <= N; i++) {
        cin >> h;
        while (true) {
            if (st.empty()) {
                cout << "0 ";
                st.push({i, h});
                break;
            } else {
                if (st.top().second >= h) { // 이전 탑이 크거나 같으면
                    cout << st.top().first << " ";
                    st.push({i, h});
                    break;
                } else { // 이전 탑이 작으면
                    st.pop();
                }
            }
        }
    }
    return 0;
}