[백준 골드4] 17298 오큰수

https://www.acmicpc.net/problem/17298
 
 
오큰수는
현재 수보다 크면서 오른쪽에 있는 수만 구하면 된다.
 
생각은 간단한데 스택으로 시간 초과 안뜨고 풀 수 있어야 한다.
 
-1로 초기화 해놓고 쓰면 예외처리를 따로 해주지 않아도 된다.
스택을 이용해서 인덱스를 담아두고 꺼내쓰는 식으로 값을 비교하고,
비교한 값이 크다면 정답이 되는 ans 배열에 넣어주면 된다.
 
그럼 오른쪽에 위치하며 자신보다 큰 값이 없던 친구들은 자동으로 -1이 되고,
그렇지 않은 값들은 가까우면서 큰 수를 구할 수 있다.

https://www.acmicpc.net/problem/17298

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;


int main(void)
{

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

    
    int n;
    cin >> n;
    vector<int> arr(n, -1);
    vector<int> ans(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    stack<int> stk;
    stk.push(0);

    for (int i = 1; i < n; i++) {
        while (!stk.empty() && arr[stk.top()] < arr[i])
        {
            ans[stk.top()] = arr[i];
            stk.pop();
        }
        stk.push(i);
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    

    return 0;
}