[17729] 오등큰수 #python

백준 17299번 오등큰수

  

    
    
    
    
  
import sys

num = int(input())
a = list(map(int, input().split(" ")))
result = ["-1" for _ in range(num)]
stack = [0]
count = dict()
for i in a:
    try:
        count[i] += 1
    except:
        count[i] = 1

for i in range(num):
    while stack and count[a[stack[-1]]] < count[a[i]]:
        result[stack[-1]] = str(a[i])
        stack.pop()
    stack.append(i)
    i+=1

print(" ".join(result))

[17298]오큰수와 같은 유형의 문제이다. 다만, 오등큰수는 각 원소 별 합에 대한 크기를 비교한다.

count에 원소를 키로 해서 키 별 원소 개수를 저장한다.

stack에는 a의 인덱스 값을 저장할 건데, for문을 돌면서 count[a] 값이 작은 a의 인덱스를 stack에 push하다가 stack[-1]보다 큰 count[a]를 만나면 stack에서 인덱스를 pop한다.