BackJoon_오큰수(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)을 공백으로 구분해 출력한다.

예제

• Example 1:

Input:
4
3 5 2 7

Output:
5 7 7 -1

• Example 1:

Input:
4
9 5 4 8

Output:
-1 8 8 -1

코드

#pragma warning (disable : 4996)

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

int ans[1000001];
int seq[1000001];

int main()
{
    int N;
    stack<int> s;

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> seq[i];

    for (int i = N - 1; i >= 0; i--)

    {
        while (!s.empty() && s.top() <= ans[i])
            s.pop();

        if (s.empty()) ans[i] = -1;
        else ans[i] = s.top();

        s.push(seq[i]);
    }

    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";

    return 0;
}

풀이

	//1.
    for (int i = N - 1; i >= 0; i--)
    {
    	//4.
        while (!s.empty() && s.top() <= ans[i])
            s.pop();
		
        //2.
        if (s.empty()) ans[i] = -1;
        else ans[i] = s.top();

		//3.
        s.push(seq[i]);
    }

1. 문자열의 뒷부분 부터 탐색을 시작한다.
   마지막 원소부터 차례대로 스택에 push 하면서 이전의 문자열들과 비교를 할 것이다.

2. 마지막 원소 or 오른쪽에 큰 수가 없는 수는 '-1' 의 값을 가진다.
   현재의 인덱스의 값 < 스택의 top() 이라면 스택의 top()이 오큰수가 된다.

3. 현재의 인덱스의 값은 다음 비교를 위해 스택에 push 한다.

4. 스택의 top이 현재의 인덱스의 값보다 작다면 더 이상 필요 없으니 pop 한다.

결과

Runtime 588 ms / Memory 12308 KB

---

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