(2024 대회 준비) 오큰수 - 17298번

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제 입력1

4
3 5 2 7

예제 출력1

5 7 7 -1

예제 입력2

4
9 5 4 8

예제 출력2

-1 8 8 -1

코드

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int a[1000001];
int b[1000001];

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    stack<int> s;
    int data;

    for (int i = 0; i < N; i++)
    {
        cin >> data;
        a[i] = data;
    }

    for (int i = 0; i < N; i++)
    {
        while (!s.empty() && a[s.top()] < a[i])
        {
            b[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }

    while (!s.empty())
    {
        b[s.top()] = -1;
        s.pop();
    }

    for (int i = 0; i < N; i++)
    {
        cout << b[i] << " ";
    }
}

설명

스택을 사용하여어서 푸는 문제이다.

처음 원소[인덱스]를 스택에 넣는다.

그리고 다음 원소내용과 스택 가장 위쪽 있는 인덱스의 내용과 비교해서 다음 원소내용이 더 크면

스택에서 꺼내고 그 원소내용을 스택 가장 위쪽에 있는 인덱스의 내용으로 넣는다.

아니면 다시 스택에 집어넣는다

이 행위를 반복하면 된다.