백준 17298 - 오큰수

www.acmicpc.net/problem/17298

 

오큰수를 더 쉽게 말하면 수열에 있는 어떤 수가 처음으로 만나는 자신보다 큰 수이다.

 

큰 수의 입장에서 생각해보자. 예를 들어 다음과 같은 수열이 있을 때

 

5 4 3 2 1 7

 

7을 제외한 모든 수의 오큰수는 7이 된다.

 

이를 잘 관찰하면 수열에서 어떤 수보다 왼쪽 방향으로 작은 수들은 모두 오큰수를 가질 수 있다는 것을 발견할 수 있다.

 

수열에 대해 반복문을 돌면서 while문을 이용해 스택에 마지막으로 올려진 항보다 현재 항이 크면 스택에 올려진 항을 pop하고 pop된 항의 오큰수를 현재 항으로 저장하면 수열의 모든 오큰수를 구할 수 있게 된다.

 

이렇게 오큰수를 모두 구한 뒤 출력해주면 정답을 받을 수 있다.

 

전체 코드

#include <bits/stdc++.h>
     
using namespace std;
using pii = pair<int, int>;
  
int n;
int ar[1000000];
int res[1000000];
stack<pii> nge;
 
int main()
{
    memset(res, -1, sizeof res);
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; ++i)
        cin >> ar[i];
    
    for (int i = 0; i < n; ++i)
    {
        while (nge.size() && nge.top().first < ar[i])
        {
            pii x = nge.top();
            nge.pop();
            res[x.second] = ar[i];
        }
 
        nge.push({ar[i], i});
    }
 
    for (int i = 0; i < n; ++i)
        cout << res[i] << ' ';
}