백준 17299 - 오등큰수 [파이썬]

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

17299번: 오등큰수

 

풀이 과정

오큰수 문제와 비슷하게 접근하면 된다. 수열 A에 등장한 횟수를 배열에 저장하고, 오등큰수를 찾지 못한 수의 index를 스택에 저장한다. 그리고 다음 수를 인식하면서 stack top의 index에 해당하는 수보다 등장 횟수가 더 많으면 그 index의 해당하는 수의 오등큰수를 바꿔주면 된다.

 

코드

import sys

N = int(input())
A = list(map(int, input().split()))

NGF = [-1] * N
F = [0] * 1000010

stack = []

for i in A:
    F[i] += 1

for i in range(N):
    while len(stack) and F[A[i]] > F[A[stack[-1]]]:
        NGF[stack.pop()] = A[i]
    stack.append(i)

for i in NGF:
    print(i, end=' ')