백준 17298 오큰수 (C++)

17298번: 오큰수

스택을 활용한 문제이다. 오큰수를 주어진 수열 뒤부터 구하는 방식으로 풀었다. 반복문을 활용해 수열 뒤부터 접근을 시작하며 스택이 비엇는지 확인한다. 여기서 스택은 오큰수 후보들을 저장할 곳으로 사용되며 오름차순에 해당하는 값만 저장된다. 오큰수는 백터에 저장된다. 즉 스택이 비어있으면 오큰수가 없다는 뜻이므로 -1을 저장한다. 스택이 존재한다면 스택의 탑과 현재 값을 비교하여 오큰수에 해당하면 스택의 탑을 벡터에 저장하고 현재 값을 스택에 저장한다. 만약 현재 값보다 작다면 오큰수 후보가 아니므로 스택에서 제거하고 다시 반복한다. 이후 벡터에 저장된 오큰수를 뒤부터 출력을 해준다.
아이디어가 잘 안 떠올랐던 문제였다.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int N;
int A[1000001];
stack<int> s;
vector<int> v;

void solution() {
    for (int i = N; i > 0; i--) {
        while (!s.empty()) {
            if (s.top() > A[i]) {
                v.push_back(s.top());
                s.push(A[i]);
                break;
            }
            else {
                s.pop();
            }
        }

        if (s.empty()) {
            v.push_back(-1);
            s.push(A[i]);
        }
    }

    for (int i = v.size() - 1; i >= 0; i--) {
        cout << v[i] << " ";
    }
}

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

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}