오등큰수

문제

1. 크기가 N인 수열 A = A(1), A(2), ..., A(N)
2. 수열A 에서 A(1)이 등장한 횟수를 F(1)
3. A(i)의 오등큰수(NGF(i))는 오른쪽에 있으면서 수열A에서 등장한 횟수가 F(i)보다 큰수,
   그런한 수가 없는 경우에는 오등큰수(NGF(i))는 -1
4. 총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

나의 풀이

import sys
from collections import Counter
N = int(input())
numbers = list(map(int,sys.stdin.readline().split()))
counter = Counter(numbers)
F = dict(counter)
answer = [-1 for i in range(n)]
i = 1
stack = [0]
while i < n:
   while stack and F[numbers[stack[-1]]] < F[numbers[i]]:
       s[stack[-1]] = numbers[i]
       stack.pop()
   stack.append(i)
   i += 1
print(*answer, end = " ")

원리

1. while stack and F[numbers[stack[-1]]] < F[numbers[i]]:

• stack에는 numbers의 index들이 쌓인다.
  -> 만약 numbers[i]의 오른쪽 수보다 F()가 작을시 stack에 쌓아준다.
  이는 F()의 수가 왼쪽수들보다 큰수(big)가 나왔을때 바꿔줄 수들의 index를 알기 위해서이다.
• 바꾸어줄 index번호를 알고난후 answer[index] 를 numbers에서의 숫자(numbers[big])로 바꾸어준다.

2. stack.append(i)
   i += 1

• 오른쪽 수의 F()가 크지 않을 경우는 stack에 i를 쌓아준다.
  -> F()가 큰수가 나왔을경우 처리해주기 위해서