[백준 골드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;
}