백준 17299 오등큰수 (C++)

17299번: 오등큰수

스택을 이용한 문제이다. 문제에서 구해야할 것은 현재값보다 오른쪽에 위치하면서 카운트가 가장 큰 왼쪽에 있는 값이다. 먼저 문제를 입력받으면서 해당 값을 카운트를 해주었다. 그리고 NFG를 -1로 초기화를 해주고 반복문을 돌면서 오등큰수를 찾아주었다. 찾는 방법은 스택을 이용해주었는데 스택에 값을 차례대로 넣어주면서 해당 인덱스의 값 카운트가 스택의 top 인덱스에 해당하는 값의 카운트보다 클 경우 이를 NFG에 저장하고 스택을 pop해주기를 반복해주었다. NFG를 모두 구한 후 이를 출력해주었다.
아이디어가 쉽게 떠오르지 않았던 문제였다. 단순히 완전 탐색으로 찾기에는 N 범위가 커서 시간 초과가 날 것이 뻔했기에 스택을 이용한다는 점은 생각해 냈었는데 이를 어떻게 이용하여 오등큰수를 구할 지 잘 떠오르지가 않았었다. 다른 사람들의 아이디어를 참고하여 문제를 풀었다. 좀 더 많은 문제들을 풀어봐야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int N;
int A[1000000];
int F[1000001];
int NFG[1000001];

void solution() {
    for (int i = 0; i < N; i++) {
        NFG[i] = -1;
    }

    vector<int> v;

    for (int i = 0; i < N; i++) {
        while (!v.empty() && F[A[v.back()]] < F[A[i]]) {
            NFG[v.back()] = A[i];
            v.pop_back();
        }

        v.push_back(i);
    }

    for (int i = 0; i < N; i++) {
        cout << NFG[i] << " ";
    }
}

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]]++;
    }

    solution();

    return 0;
}