(17299) 오등큰수

https://www.acmicpc.net/problem/17299

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 3번째

 

 

 

오큰수와 동일하지만 수열의 값 대신 등장 횟수를 기준으로 해야 하는 문제.

등장 횟수는 수열을 한 번 순회하며 카운팅하면 되며, 나머지는 오큰수와 동일하다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), f(1000001);
  
  for(int i=1;i<=n;i++){
    cin >> v[i];
    f[v[i]]++;
  }
  
  stack<int> s;
  s.push(0);
  f[0]= 1000001;
  
  for(int i=1;i<=n;i++){
    while(f[v[s.top()]]<f[v[i]]){
      v[s.top()]= v[i];
      s.pop();
    }
    
    s.push(i);
  }
  
  while(!s.empty()){
    v[s.top()]= -1;
    s.pop();
  }
  
  for(int i=1;i<=n;i++)  cout << v[i] << " ";
  
  return 0;
}