[알고리즘] 백준 17299 오등큰수 // 스택

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

* 풀이

• 오큰수의 유사문제
• stack을 이용해서 오큰수를 찾은 애들을 지워버린다. => 시간복잡도를 줄임
• F[cur]이 F[top]보다  더큰경우 -> cur이 오큰수임, 기록, pop, 반복
• push(cur)
• 남아있는 애들은 오큰수가 없는애임 -> -1 기록

* 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n;
vector<ll> arr;
stack<pair<ll,ll>> s;
ll F[1000000+4],ans[1000000+4];
ll ret;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n ;

    for (int i = 0; i < n; ++i) {
        ll tmp;
        cin >> tmp;
        F[tmp]++;
        arr.push_back(tmp);
    }

    s.push({0,arr[0]});
    for (int i = 1; i < n; ++i) {
        while(s.size() && F[s.top().second] < F[arr[i]]) {
            ans[s.top().first] = arr[i];
            s.pop();
        }
        s.push({i, arr[i]});
    }

    while(s.size()) {
        ans[s.top().first] = -1;
        s.pop();
    }

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

    
    return 0;
}