백준 18298 - 오큰수

문제 설명 

 

 

 

=>이해하는데 오래 걸린 문제이다. 

=>stack을 사용하여 푸는 문제이다. 

=>stack에 들어가는 숫자는 현재 오큰수를 찾지 못한 수의 idnex이다. 

=>현재 index에 들어있는 값이 stack의 top index에 해당하는 값보다 크면 해당  top index의 오큰수를 찾게 된다. 

 

***

while(!st.empty() && arr[i]>arr[st.top()] ) 은 제대로 동작하지만, 

while(arr[i]>arr[st.top() && !st.empty() ] 은 제대로 동작하지 않는다. 

 

=> 이유는 stack의 값이 비어있을 때 top를 참조할 수 없기 때문인데, empty로 먼저 거를 경우 제대로된 동작을 할 수 있다. 

 

 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin>>N;
    int tmp;
    vector<int> arr;
    vector<int> NGE(N, -1);
    for(int i=0; i<N; ++i)
    {
        cin>>tmp;
        arr.push_back(tmp);
    }
    
    stack<int> st;
    
    
    for(int i=0;i<N; ++i)
    {
        while(!st.empty() && arr[i]>arr[st.top()] )
        {
            NGE[st.top()]=arr[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0; i<N; ++i) cout<<NGE[i]<<" ";
    
    return 0;
}