[ 백준 ] 17298번 - 오큰수 (C++)

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

17298번: 오큰수

 

 

[ 문제풀이 ]

 

1. stack이 비어있지 않고, n의 값이 stack.top보다 클 경우 st.pop을 해주고, st이 완전히 비기 전까지 반복해 줍니다.

 

2. arr 배열을 만들고, 1의 st.pop 과정에서 arr 배열의 해당 숫자의 idx  값을 n으로 갱신합니다. 

 

3. st에 n을 push 합니다.

 

4. arr 배열을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<stack>
 
using namespace std;
 
int N;
int arr[1000001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    fill(arr, arr + N + 1, -1);
 
    stack<pair<int, int>> st;
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
 
        if (!st.empty()) {
            while (st.top().first < n) {
                arr[st.top().second] = n;
                st.pop();
                if (st.empty()) break;
            }
        }
 
        st.push({ n,i });
    }
 
    for (int i = 1; i <= N; i++) {
        cout << arr[i] << ' ';
    }
}