백준 17299번 오등큰수 - C++ 풀이

---

 

1. 오큰수와 동일하게 스택을 이용하여 풀이한다.

 

1. 오큰수와 동일하게 스택을 이용하여 풀이한다.

 오큰수 문제와 같은 풀이를 적용할 수 있다. Ai 대신 F(Ai)값을 가지고 비교한다는 차이만 있다.

백준 17298번 오큰수 - C++(cpp) 풀이 + 그림 설명

반응형

---

#include <iostream>
#include <stack>

using namespace std;

const int MAX = 1000001;

int N;
int A[MAX], F[MAX], NFG[MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> A[i];
        F[A[i]]++;
    }
    
    stack<int> s;
    
    for (int i=N-1; i>=0; i--) {
        while (!s.empty() && F[s.top()] <= F[A[i]]) s.pop();
        
        if (s.empty()) NFG[i] = -1;
        else NFG[i] = s.top();
        
        s.push(A[i]);
    }
    
    for (int i=0; i<N; i++) cout << NFG[i] << " ";
    
    return 0;
}