백준 17299 : 오등큰수

문제 설명

---

주어진 수열에서 각 원소의 등장 빈도를 계산한 후, 각 원소의 오른쪽에서 그보다 더 높은 빈도를 가진 첫 번째 수를 찾아 오등큰수로 설정. 만약 그런 수가 없다면, 해당 원소의 오등큰수는 -1로 설정. 이를 통해 모든 원소에 대해 오등큰수를 구하는 문제.

---

 

문제 자체는 오큰수와 비슷하다. 오큰수에서 빈도수 계산이 추가된 문제이다.

 

1. 수열의 각 원소의 등장 빈도를 계산.

 

2. 수열을 처음부터 끝까지 순회하면서 스택을 사용해 각 원소의 오등큰수를 계산.

 -스택이 비어 있으면 현재 원소와 인덱스를 스택에 넣는다.

 -스택이 비어 있지 않으면, 스택의 맨 위 원소와 현재 원소의 등장 빈도를 비교.

     -현재 원소의 등장 빈도가 더 크면, 스택의 맨 위 원소의 오등큰수 현재 원소. 스택에서 해당 원소를 제거하고 ans 배열에 결과를 저장.

     -현재 원소의 등장 빈도가 작거나 같으면, 비교를 멈추고 현재 원소를 스택에 추가.

---

소스 코드

#include <stdio.h>
#include <algorithm>
#include <stack>

using namespace std;

int n;
stack <pair<int, int>> st;
int ans[1000010], arr[1000010];
int cnt[10000010];

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
    }
    for(i=0;i<n;i++) {
        int x = arr[i];
        if(st.empty()) st.push({x, i});
        else {
            while(!st.empty()) {
                int t = st.top().first;
                if(cnt[t] < cnt[x]) {
                    int sec = st.top().second;
                    ans[sec] = x;
                    st.pop();
                }
                else break;
            }
            st.push({x, i});
        }
    }
    while(!st.empty()) {
        ans[st.top().second] = -1;
        st.pop();
    }
    for(i=0;i<n;i++) printf("%d ", ans[i]);
    return 0;
}