백준 2493 - 탑 [C++]

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

2493번: 탑

---

풀이 과정

탑이 왼쪽으로 레이저를 쏠 때, 먼저 만나는 높이가 쏜 탑보다 크거나 같은 탑에 레이저가 도달하는데, 각 탑에서 쏜 레이저는 어떤 탑에서 수신하는지 출력하는 문제이다.

 

스택에 탑의 높이와 인덱스를 넣는다. 다음 건물이 들어왔을 때, 건물의 높이보다 크거나 같은 높이가 나올때 까지 스택 탑의 원소를 비운 후, 스택 탑의 index를 출력하면 그 index의 탑 높이는 입력받은 건물의 높이보다 같거나 클 것이므로 레이저가 도달할 것임을 알 수 있다.

---

소스 코드

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

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

    stack<pair<int, int>> st;
    st.push(make_pair(100000001, 0));

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        while (st.top().first < num) {
            st.pop();
        }

        cout << st.top().second << ' ';

        st.push(make_pair(num, i));
    }

    return 0;
}