BOJ 2493 : 탑

• 문제 링크 : boj.kr/2493
• 난이도 : G5
• 태그 : 스택

2493번: 탑

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    stack<pii> _st;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        while(!_st.empty()) {
            if(_st.top().first >= input) {
                break;
            }
            _st.pop();
        }
        cout << (_st.empty() ? 0 : _st.top().second + 1) << " ";
        _st.push({input, i});
    }

    return 0;
}

---

풀이

가장 단순하게 생각해보면 i번째 탑의 레이저가 어디에 도달하는지 확인하기 위해 i-1부터 1번째 탑까지 확인할 수 있다.

다만 이렇게 할 경우 시간복잡도가 $O(N^2)$으로 시간초과가 발생한다.

 

필요하지 않은 확인을 제거해보자.

k번째 탑의 높이를 $A_k$라고 한다면 $i < j$이고 $A_i < A_j$라면 j번째 이후의 탑에서는 i번째 탑을 확인할 필요가 없다. i번째 탑에 도달할 신호는 j번째 탑에 먼저 도달하기 때문이다.

따라서 우리가 확인해야 할 탑의 높이를 순번대로 나열한 배열의 k번째 원소를 $B_k$라고 했을 때, $i<j$라면 $B_i > B_j$이다. 새로운 원소 $B$가 추가되었을 때, $B_k < B$인 모든 $B_k$를 제거하고 $B$를 배열에 추가한다.

 

앞의 배열은 스택을 이용하여 쉽게 관리할 수 있다.

현재의 탑의 높이보다 낮은 값은 스택에서 pop하고 현재의 값을 스택에 push해주면 된다.