BOJ 17298. 오큰수

BOJ 17298. 오큰수

랭크 : 골드4

문제 풀이

문제를 잘못 읽어서 한참 해맸습니다. 그냥 뒤에서 부터 큰 거에서 작은 순으로 스택이 쌓이도록 만들고, 이를 참조해서 값을 배정하도록 하면 됩니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N, tmp;
int ans[1'000'001];

int main() {
    fastio;
    cin >> N;
    stack<int> s;
    for (int i = 0; i < N; i++)
        cin >> ans[i];
    for (int i = N - 1; i >= 0; i--)
    {
        while (!s.empty() && s.top() <= ans[i])
            s.pop();
        if (s.empty()) tmp = -1;
        else tmp = s.top();
        s.push(ans[i]);
        ans[i] = tmp;
    }
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
}

알고리즘	시간복잡도	공간복잡도
stack	$O(N)$	$O(N)$