백준 17299번 오등큰수

문제 링크 : https://www.acmicpc.net/problem/17299

17299번: 오등큰수

풀이

스택 문제입니다!

17298번 오큰수 문제랑 거의 비슷한 문제입니다.

17298번 오큰수 문제 참조 : https://suhwanc.tistory.com/58

다른 점은 미리 원소의 개수를 카운트 한다는 점인데,

이 카운트를 이용해 고대로~ stack 작업할 때 써먹으면 된다!

 

소스 코드

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
int f[1000001];
int main()
{
    
    int n; scanf("%d", &n);
    vector<int> a(n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        f[a[i]]++; //개수 카운트
    }
 
    vector<int> ans(n);
    stack<int> s;
    s.push(0); //처음 idx 저장
 
    for (int i = 1; i < n; i++) {
        if (s.empty()) s.push(i);
        while (!s.empty() && f[a[s.top()]] < f[a[i]]) { //오등큰수 발견 시
            ans[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) {
        ans[s.top()] = -1;
        s.pop();
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}
 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~