백준 17299 - 오등큰수

문제 설명 

 

 

 

 

=> 오큰수와 같은 개념의 문제이다. 

https://codingham.tistory.com/77

백준 18298 - 오큰수

위를 보면 오큰수를 구하는 코드를 알 수 있다. 

 

=>이 문제에서 본인은 세개의 배열을 써서 문제를 풀었다. 

=>

arr  : 실제값을 입력받는 배열
arr2 : 각 숫자가 나온 횟수를 arr의 길이로 다시 만든 배열 
cntarr : 각 element를 세는 배열 

 

=> 다른 사람들의 풀이를 보면 훨씬 간단하게 푼 걸 볼 수 있었다.

=> 아직은 그 답이 어떻게 나왔는지 이해를 하지 못해, 나의 방법으로 풀었다. 

 

 

 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin>>N;
    int tmp;
    vector<int> arr;
    int cntArr[1000001]={0};
    vector<int>arr2(N);
    vector<int> NGF(N, -1);
    
    for(int i=0; i<N; ++i)
    {
        cin>>tmp;
        cntArr[tmp]++;
        arr.push_back(tmp);
    }
    
    for(int i=0; i<N; ++i)
    {
        arr2[i]=cntArr[arr[i]];
    }
    
    stack<int> st;
    
    
    for(int i=0;i<N; ++i)
    {
        while(!st.empty() && arr2[i]>arr2[st.top()] )
        {
            NGF[st.top()]=arr[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0; i<N; ++i) cout<<NGF[i]<<" ";
    
    return 0;
}