BOJ 17299 오등큰수

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

17299번: 오등큰수

 

어떠한 수보다 보다 등장 횟수가 많으면서 오른쪽에 등장하는 수를 구하는 문제입니다. 오른쪽에 등장하는 수라는 점에서 감을 잡을 수도 있는데, stack을 사용하여 등장 횟수의 내림차순으로 인덱스들을 관리해주면 됩니다. 스택의 위에 있는 인덱스보다 등장 횟수가 많은 수를 현재 보고 있을 경우, 현재 보고 있는 수가 해당 인덱스의 오등큰수가 됩니다. 이를 배열을 돌면서 실행해주면 각 수의 오큰수를 구할 수 있습니다. 마지막까지 스택에 남아 있는 수의 경우 오등큰수가 -1이 되게 됩니다.

 

딱 보고 아 스택으로 풀겠구나 싶어서 풀었는데 한 번에 맞아서 기분이 좋습니다. 좀 typical한 문제기는 하지만 골드3을 보자마자 푼 건데 조금 뿌듯해해도 되지 않을까요? 아님망고

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define FF first
#define SS second
#define pii pair<int,int>

using namespace std;

int T, n, vec[1000010], cnt[1000010], ans[1000010];

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> n;

        for (int i = 0; i < n; i++) {
            cin >> vec[i];
            cnt[vec[i]]++;
        }

        stack<pii > s;
        s.push({-1, n + 10});

        for (int i = 0; i < n; i++) {
            while (s.top().SS < cnt[vec[i]]) {
                ans[s.top().FF] = vec[i];
                s.pop();
            }
            s.push({i, cnt[vec[i]]});
        }

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

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

    return 0;
}