오큰수

문제를 본다 -> 시간제한 1초이다.

1. 완탐으로 풀생각을 해본다 -> O(N^2)이 나온다.

2. 그러면 다른 여러 알고리즘들을 생각해본다.

3. 마땅한게 없다 -> 그리디 (최적의 경우의 수)를 생각한다.

4. -> 짝찟기 문제와 비슷하다 -> "stack"을 사용한다.

이문제는 스택을 배열과 어떻게 신박? 하게 사용을 하느냐 문제인거 같음.

값은 스택에 넣지않고 배열에 넣고 스택에는 배열의 인덱스를 넣는다.

또한 cstring헤더의 memset의 사용

1번 생각을 하고 2번 4번으로 생각을 함.

스택을 사용하고 큐까지 사용했는데 뭐 어떻게 스택을 사용을 해야할지를 모르겠음.

스택을 활용하는것 까지 왔다면은

애매한 순간에는 push를 해라.

cpp코드

#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 1000002

int n, arr[MAX], ret[MAX];
stack<int> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    memset(ret, -1, sizeof(ret));
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        while (s.size() && arr[s.top()] < arr[i])
        {
            ret[s.top()] = arr[i]; s.pop();
        }
        s.push(i);
    }

    for (int i = 0; i < n; ++i) 
        cout << ret[i] << " ";
    return 0;
}