백준 17299. 오등큰수 (Python)

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

풀이

오등큰수:

• 수열 li가 주어질 때, li[i]의 오등큰수는 j(i<j)이면서 li[i]보다 등장횟수가 많으면서 가장 작은 j를 뜻한다.
• 즉, 수열li에서 li[i]보다 오른쪽에 있으면서 li[i]보다 등장횟수가 큰 수열값을 찾는것이 관건이다.
  ex)
  li=[1,1,2,3,4,2,1] 일때,
  등장횟수는 F(1)=3, F(2)=2, F(3)=1, F(4)=1
  오등큰수는
  NGF(0)=li[0]인 1보다 많이 등장한 값은 없으므로 -1
  NGF(1)= 동일
  NGF(2)= li[2]인 2보다 많이 등장한 값은 1밖에 없으므로 1
  NGF(3)= li[3]인 3보다 많이 등장한 값은 1, 2인데 2가 오른편에 있으면서 가장 가까우므로 2
  NGF(4)= li[4]인 4는 위의 NGF(3)과 동일, 2
  NGF(5)= li[5]인 2보다 많이 등장한 값은 오른쪽에서 1밖에 없으므로 1
  NGF(6)= li[6]인 1보다 오른쪽에 있는 값은 없으므로 -1

스택을 이용해 구현한다.
먼저, 수열 li에서 등장횟수를 구해준다
ex) li[2]=3 이므로 li2[3]= li[2]의 등장횟수 3

이후, li 수열을 순회한다
이때, 결과배열 res는 -1로 초기화 해준다.

• stack이 비어있지 않고 stack의 마지막 값보다 현재 수열의 등장횟수가 더 많은경우,
  - 결과값에 stack의 마지막 값(인덱스)를 넣고 stack에서 pop!
• 현재 수열의 인덱스(i)를 stack에 append

import sys
input=sys.stdin.readline
N=int(input())
li=list(map(int,input().split()))
li2=[0]*(max(li)+1)
res=[-1]*(len(li))
stk=[]
for i in li:
    li2[i]+=1
for i in range(N):
    while stk:
        if li2[li[stk[-1]]]<li2[li[i]]:
            res[stk.pop()]=li[i]
        else:
            break
    stk.append(i)
print(*res)