[백준] 17298번 오큰수 (C++)

문제 링크

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

17298번: 오큰수

 

문제 설명

크기가 N인 수열이 주어지며, 수열의 각 원소에 대한 오큰수 NGE(i)를 구한다.

오큰수는 해당 원소의 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 수를 의미한다.

그러한 수가 없는 경우에는 오큰수는 -1이다.

 

예를 들어 A = [9,5,4,8]인 경우,

NGE(1) = -1 (9보다 큰 수가 오른쪽에 없으므로)

NGE(2) = 8 (5보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽의 수는 8이므로)

NGE(3) = 8 (4보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽의 수는 8이므로)

NGE(4) = -1 (8보다 오른쪽에 있으면서 큰 수가 없으므로)이다.

 

사고 과정

시간제한이 1초이고 N의 최댓값이 1,000,000이기 때문에

단순한 배열의 선형 탐색으로 접근하면 시간 초과가 뜰 것이다.

 

왼쪽에 있는 원소의 오큰수를 구하려면 오른쪽 원소들의 정보가 필요한데,

오른쪽 원소들의 정보 중 불필요한 정보들을 제거하면 실행 시간이 감소되지 않을까 생각했다.

왼쪽 원소들이 오른쪽 원소들의 정보가 필요한 것이므로,

오큰수를 구하는 과정을 오른쪽에서부터 왼쪽으로 나아가 보자.

 

A = [3, 4, 6, 12, 8, 9, 11]인 경우를 생각해보자.

1. 가장 마지막 원소인 11은 당연하게도 오큰수가 -1일 것이다.

2. 그다음 원소인 9의 경우, 오큰수를 구하려면 바로 오른쪽의 원소의 정보가 필요하다.

3. 8의 경우 오큰수는 9가 되는데, 바로 오른쪽의 원소가 자신보다 크기 때문이다.

    8의 오큰수를 계산할 때는 11이라는 정보가 필요하지 않았다.

    하지만 만약 10이었다면, 11이라는 정보가 필요했을 것이다.

4. 11의 오큰수는 -1이 된다. 이를 구하기 위해서는 11의 오른쪽에 있는 모든 원소들을

     탐색할 필요가 있다.

5. 6의 오큰수는 12가 된다. 12의 오른쪽에 있는 원소들의 정보는 필요하지 않았다.

     이는 6이 아니라 다른 어떤 수 (e.g. 1, 100, 1000...)가 되어도 동일한데, 

     12의 오른쪽에는 12보다 큰 수가 없기 때문에 12가 오큰수가 되지 않는다면

     다른 어떤 수도 오큰수가 될 수 없기 때문이다.

    즉, 오른쪽에서 왼쪽 순서로 오큰수를 구할 때 오른쪽에 있는 수 들보다 큰 수가 있다면,

    (이 경우에는 12) 오른쪽 원소의 정보는 필요 없어지고, 탐색 시간이 줄어들 것이다.

6. 4의 오큰수는 6이 된다. 6은 12보다 작기 때문에 필요한 원소이다.

7. 3의 오큰수는 4가 된다. 4는 6보다 작기 때문에 필요한 정보로서 남아있어야 한다.

    만약 4가 6보다 큰 수인 7이라면, 7이 오큰수가 되지 않으면 6 또한 오큰수가 될 수 없으므로

    6이라는 정보는 더 이상 필요하지 않을 것이다.

 

해결 과정

위의 과정을 구현하기 위해 스택을 활용하였으며, 

오큰수의 탐색은 위와 동일하게 오른쪽 원소에서 왼쪽 원소 순서로 진행하였다.

 

만약 스택의 크기가 0이라면 출력용 배열인 result의 알맞은 인덱스에 -1을 넣고 스택에 값을 넣는다.

 

스택의 크기가 0이 아닐 경우에는 스택의 가장 위의 원소(이하 스택 원소)와

오큰수를 구하고자 하는 원소(이하 배열 원소)의 값을 비교한다.

 

만약 배열 원소의 값이 스택 원소의 값보다 작다면 해당 배열 원소의 값이 필요하다는 의미이므로,

(다음 배열 원소의 값이, 즉, 현재 배열의 원소보다 왼쪽에 있는 값이

 현재 배열의 원소보다 작을 수 있으므로 현재 배열의 원소 값이 필요하다.)

스택에 값을 넣고 result에 스택 원소의 값을 넣는다.

 

만약 배열 원소의 값이 스택 원소의 값보다 크다면

배열 원소의 값이 스택 원소의 값보다 작아질 때까지 (혹은 스택이 빌 때까지) 스택의 값들을 제거한다.

위의 예시의 경우, 배열 원소가 12일 때 스택에 있는 8, 9, 11의 값들은 차례대로 제거될 것이다.

 

이 과정을 거쳤을 때 스택이 비어있다면 해당 배열 원소 값의 오큰수가 없다는 뜻이므로

result에 -1을, 스택에 해당 원소 값을 집어넣는다.

 

만약 스택에 값이 존재한다면 현재 스택 원소가 배열 원소의 오큰수가 될 것이므로

result에 스택 원소를, 스택에 해당 원소를 집어넣는다.

 

위의 예제를 활용한 flow는 다음과 같다.

코드

#include <iostream>
#include <vector>

using namespace std;

#define MAX 1000001

int N;
int arr[MAX];
int result[MAX];
vector<int> stack;

void init();
void input();
void solve();
void output();

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

void input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
}

void solve()
{
    for (int i = N - 1; i >= 0; i--)
    {
        if (stack.size() == 0)
        {
            result[i] = -1;
            stack.push_back(arr[i]);
        }
        else
        {
            if (arr[i] < stack.back())
            {
                result[i] = stack.back();
                stack.push_back(arr[i]);
            }
            else
            {
                while (stack.size() > 0 && stack.back() <= arr[i])
                {
                    stack.pop_back();
                }

                if (stack.size() == 0)
                {
                    result[i] = -1;
                    stack.push_back(arr[i]);
                }
                else
                {
                    result[i] = stack.back();
                    stack.push_back(arr[i]);
                }
            }
        }
    }
}

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

int main()
{
    init();
    input();
    solve();
    output();

    return 0;
}