오등큰수 //17299

• 문제
  크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.
  Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.
  예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.
  
  //시간 제한: 1초, 메모리 제한: 512MB

• 입력
  첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

• 출력
  총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

// Created by dongwan-kim on 2022/07/25.
#include<iostream>
#include<stack>
#include<vector>

using namespace std;

int n, arr[10000000], cnt[10000000];
stack<pair<int, int>> s, p;
stack<int> ans;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {		//숫자 나온 횟수 입력받기
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    for (int i = 0; i < n; i++) {		//스택에 빈도수와 숫자 넣어주기
        s.push({cnt[arr[i]], arr[i]});
    }


    while (!s.empty()) {
        while (!p.empty() && s.top().first >= p.top().first) {
            p.pop();
        }
        if (p.empty()) {
            ans.push(-1);
            p.push(s.top());
            s.pop();
        } else {
            ans.push(p.top().second);
            p.push(s.top());
            s.pop();
        }
    }

    while (!ans.empty()) {
        cout << ans.top() << " ";
        ans.pop();
    }

}

풀이

오큰수 문제와 매우 비슷한 유형이다.
https://velog.io/@ehddhks194/%EC%98%A4%ED%81%B0%EC%88%98-17298
오큰수 풀이는 위 링크에 있다.

오큰수와 차이점은 입력받은 숫자의 크기로 비교하는 것이 아니라 숫자의 빈도수를 비교하여 출력하는 것이다.
그래서 스택에 pair를 넣어서 first에는 빈도수, second에는 숫자를 담아 문제를 해결했다.

위와 같은 방식으로 풀었더니 오답이 나왔는데 이유는 pair끼리 비교 연산을 사용할 때 first나 second를 명시해주지 않으면 first끼리 비교하기 때문에 빈도수를 first에 넣고 구현하였는데, first가 같은 경우 second의 대소를 비교하기 때문에 빈도수는 같은데 숫자가 더 크면 오큰수가 되어버린 것이다.

위의 부분을 처리하기 위해 조건문에 s.top().first로 명시해 주었고, 문제를 해결할 수 있었다.