[BOJ/C++] 2493번: 탑

문제

 

풀이

N은 500000 이하이고, 제한 시간은 1.5초이므로 O(n^2) 풀이로는 해당 문항을 해결하지 못한다.

출력 양식에서 하나씩 값을 출력할 때, 앞에 있는 것 전부를 조사하지 않고 일부만 조사해서 답을 얻을 수 있는 알고리즘을 구상해야함에 주의하며 생각해보자.

오른쪽 탑 A가 왼쪽 탑 B보다 높이가 높다면, A보다 오른쪽 탑들에 대해서는 B의 정보가 필요가 없어진다. 왜냐하면 B까지 가기 전에 A에 막힐 것이기 때문이다.

따라서 스택을 활용하여 현재 탑을 쌓을 것인데, 현재보다 높이가 작은 탑을 pop하여 없애버리고, 현재 높이 이상인 처음 만난 탑부터를 남겨두는 과정을 반복하면, 탐색에 걸리는 시간이 O(1)이 되므로, 종합적으로 O(N) 시간에 해결이 가능하다.

코드

#include <bits/stdc++.h>
using namespace std;

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

    int n, arr[500010];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    deque<pair<int, int>> st; // number, height
    for (int i = 0; i < n; i++) {

        while (!st.empty() && st.back().second < arr[i]) st.pop_back();
        if (st.empty()) cout << 0 << " ";
        else cout << st.back().first << " ";
        st.push_back({ i + 1, arr[i] });
    }
}