[백준]오등큰수(17299)

문제 링크 : [백준]오등큰수(17299)

17299번: 오등큰수

문제 설명

N개의 수열이 주어졌을 때, 수열 전체에 임의의 숫자(v)가 나타난 횟수를 F(v)라고 할 때,

수열의 각 수 오른쪽에 있는 수 중 F(v)가 현재 위치의 F(v)보다 큰 수 중 가장 왼쪽에 있는 값들을 구하세요.

 

입력

N(수열의 크기, 1 <= N <= 1,000,000)

Ai(수열의 값)

7
1 1 2 3 4 2 1

 

출력

-1 -1 1 2 2 1 -1

 

카테고리

#스택

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. F(x)에 대한 값을 알아야 하기 때문에, 입력을 받으면서, 각 숫자가 몇 번씩 나오는지 카운팅합니다.
2. 왼쪽부터 차례대로 보려면 기준 위치에서 오른쪽의 위치를 모두 살펴야 하기 때문에 O(N2)의 시간복잡도가 발생하게 됩니다.
3. 오른쪽에서부터 거꾸로 살펴본다면??
4. 오른쪽부터 훑게 되면, 특정 위치(x)보다 오른쪽에 있으면서, 그 위치의 F(d[x])의 값보다 작은 F(v)의 값은 필요가 없습니다.
   1. 예를들어, i가 3인 곳의 F(v)가 5, i가 4인 곳의 F(v)가 4라고 가정합니다.
   2. i가 2인 곳의 F(v)가 5보다 작다면, 3이 답이 될 것입니다.
   3. i가 2인 곳의 F(v)가 5보다 크거나 같다면, F(v)가 6 이상인 곳의 위치를 찾아야 합니다.
5. 스택을 이용하여 자신의 F(v)보다 작은 값을을 계속 빼내서 스택을 오름차순으로 만들어 답을 구하면 됩니다.

시간복잡도

O(N)

코드

#include<iostream>
#define N 1000001
using namespace std;
int n,d[N],c[N],e[N],s[N],p,i;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++)cin>>d[i],c[d[i]]++;
    for(i=n-1;i>-1;i--){
        while(p&&c[d[i]]>=c[d[s[p-1]]])p--;
        e[i]=p?d[s[p-1]]:-1;
        s[p++]=i;
    }
    for(i=0;i<n;i++)cout<<e[i]<<" ";
}