[BOJ/백준][Gold4] 17298 : 오큰수 (C++)

www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

[난이도] Gold4

[유형] Stack

 

[풀이]

1. 스택이 비어있으면 index push

2. 스택에 원소가 있을때 현재 값보다 작은 원소들은 NGE가 현재 값으로 정하고 pop

 

#include <cstdio>
#include <stack>
using namespace std;
int N,a[1000000],nge[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        nge[i]=-1;
    }
    stack<int> st;
    for(int i=0;i<N;i++){
        while(!st.empty() && a[i] > a[st.top()]) {
            nge[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0;i<N;i++) printf("%d ",nge[i]);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17298.cpp