[BOJ][C++] 백준 17299번: 오등큰수

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

17299번: 오등큰수

 

풀이

각 숫자들의 갯수는 입력을 받는 중에 cnt 벡터를 업데이트하며 구했다

입력을 다 받은 후에는 입력에 해당하는 각 숫자와 해당 숫자의 개수를 pair로 만들어서 f 벡터에 저장해준다

 

이제 f벡터를 거꾸로 돌면서 스택을 이용해 오등큰수를 구해준다

스택안에 있는 숫자들은 본인보다 오른쪽에 있는 숫자이므로 해당 스택 내에서

본인의 빈도보다 더 큰 빈도를 가진 수가 나올 때까지 pop한다.

 

그렇게 구한 오등큰수는 ngf 답벡터에 넣어준다.

나의 경우 답벡터를 어차피 거꾸로 출력해야하기 때문에 여기서도 스택을 사용해주었다.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

typedef pair<int,int> ci;

int main() {
    vector<ci> f;
    vector<int> cnt(1000001, 0);
    stack<ci> s;
    stack<int> ngf;
    
    // 입력
    int n, input;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> input;
        cnt[input]++;
        f.push_back({input, 0});
    }
    
    // 입력에 해당하는 수들의 갯수도 같이 넣어주기
    for(int i=0; i<n; i++) {
        input = f[i].first;
        f[i] = {input, cnt[input]};
    }
    
    // 스택을 이용하여 오등큰수 구하기
    s.push({-1, 1000001});
    for(int i=f.size()-1; i>=0; i--) {
        while(f[i].second >= s.top().second) {
            s.pop();
        }
        ngf.push(s.top().first);
        s.push(f[i]);
    }
    
    // 출력
    while(!ngf.empty()) {
        cout << ngf.top() << " ";
        ngf.pop();
    }
    
    return 0;
}