[Gold 4] 17298 오큰수

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

 

문제에서 오큰수는 오른쪽에 있는 가장 인접한 큰 수라고 나와있다.

따라서 기본적으로 오큰수를 찾는 방법은

2중 배열을 사용해서 구하면 된다.

 

하지만 위 방식은 O(N^2)이기 때문에 시간 초과가 발생한다.

 

따라서 스택을 사용한 방식을 사용해야한다.

스택을 사용해 오큰수를 구하는 방식은 아래와 같다.

1. 맨 뒤에 있는 수 부터 순차적으로 탐색한다.

2. 스택에 top에 있는 값이 현재 알아볼 값보다 작거나 같으면 스택에서 제거

3. 스택이 비어있다면 -1을 오큰수로 지정하거나, 스택의 top을 오큰수로 지정

4. 스택에 현재 탐색할 값을 삽입

 

위 방식을 사용하면 [3, 5, 2, 7]인 경우 아래와 같이 흘러가게 된다.

1. S : {}

A : 7

NGE : { , , ,-1}

 

2. S : {7}

A : 2

NGE : { , , 7,-1}

 

3. S : {7, 2} -> {7}

A : 5

NGE : { , 7, 7,-1}

 

4. S : {7, 5}

A : 3

NGE : {5, 7, 7,-1}

 

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

int N;
int arr[1000001];
int NGE[1000001];
vector<int> v;

int main() {

    cin>>N;

    int A;
    for(int i = 0;i<N;i++)
        cin>>arr[i];
    
    // 7 2 5 3
    for(int i = N-1;i>=0;i--){
        while(!v.empty() && v.back() <= arr[i]){
            v.pop_back();
        }
        if(v.empty())
            NGE[i] = -1;
        else
            NGE[i] = v.back();

        v.push_back(arr[i]);
    }
    for(int i = 0;i<N;i++)
        cout<<NGE[i]<<' ';
    
}