백준 #17298 오큰수

백준 #17298 오큰수

수열에서 어떤 수보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 수를 출력하는 문제.
스택을 사용해서 풀 수 있다.

vector v에 모든 입력을 받은 후, for 문으로 순회한다. 스택에는 v의 index를 저장하는데, 스택의 top이 가리키는 수보다 v[i]가 클 경우 pop하고 ans vector에 저장한다.

예시)

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <stack>

using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    stack<int> stk;
    cin >> N;
    vector<int> ans(N, -1);
    vector<int> v;
    for(int i = 0; i < N; i++) {
        int dummy;
        cin >> dummy;
        v.push_back(dummy);
    }
    for(int i = 0; i < N; i++) {
        while(!stk.empty() && v[stk.top()] < v[i]) {
            ans[stk.top()] = v[i];
            stk.pop();
        }
        stk.push(i);
    }
    for(auto it = ans.begin(); it != ans.end(); it++) {
        cout << *it << " ";
    }

    
    return 0;
}