17299: 오등큰수

import sys
from collections import Counter

N = int(input())

A = list(map(int, sys.stdin.readline()[:-1].split(' ')))
stack = []; stack.append(0) #stack에는 index를 저장
cnt = Counter(A) #각 인수의 개수를 dictionary 형태로 저장
ans = ['-1' for i in range(N)]

for i in range(1, N):
    while stack and cnt[A[stack[-1]]] < cnt[A[i]]:
        ans[stack.pop()] = str(A[i])
    stack.append(i)

print(' '.join(ans))

• N이 최대 1,000,000이라서 list의 count()를 쓰기에는 시간 초과 발생 (count()는 원소 하나 당 O(N)의 시간복잡도 -> 각 원소의 개수를 모두 구하려면 O(N^2))
• collections module의 Counter를 사용
• Counter()는 각 원소의 개수를 dictionary 형태로 반환해줌 -> O(N)의 시간복잡도를 갖음
• 오큰수를 구하는 알고리즘에서 while문의 조건문만 원소의 크기를 비교해주도록 변경해주면 됨