본인 풀이(성공)

#include<bits/stdc++.h>
using namespace std;

int n;
stack<int> stk;
map<int, queue<int>> solution;
int a[1000000];

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

    cin >> n;
    // 동일한 수 처리
    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        a[i] = temp;

        while(stk.size() && stk.top() < temp){
            solution[stk.top()].push(temp);
            stk.pop();
        }

        stk.push(temp);
    }

    while(stk.size()){
        int top = stk.top();
        stk.pop();

        solution[top].push(-1);
    }

    for (int i = 0; i < n; i++){
        cout << solution[a[i]].front() << " ";
        solution[a[i]].pop();
    }
    cout << "\n";

    return 0;
}

1. 시간초과남
2. 스택을 사용하는 로직 자체는 혼자 생각했는데 큐를 써서 그런지 몰라도 시간초과가 왜 발생하는지 도통 모르겠다.

#include<bits/stdc++.h>
using namespace std;

int n;
stack<int> stk;
int ret[1000004];
int a[1000004];

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

    cin >> n;
    // 동일한 수 처리
    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        a[i] = temp;

        while(stk.size() && a[stk.top()] < temp){
            ret[stk.top()] = temp;
            stk.pop();
        }

        stk.push(i);
    }

    for (int i = 0; i < n; i++){
        if(!ret[i]){
            cout << -1 << " ";
        }else{
            cout << ret[i] << " ";
        }
    }
    cout << "\n";

    return 0;
}

1. 배열 인덱스를 스택에 푸시하여 풀이했음
2. 큐나 맵 자료구조를 쓰면 연산에 드는 비용이 추가되어 시간초과가 발생하나보다.. 이론상으로는 괜찮은것같은데