백준 / 17299 / 오등큰수 (Stack)

n = int(input())
n_list = list(map(int, input().split()))

stack = []
dic = dict()
for i in n_list:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

result = [-1] * n
for i in range(len(n_list)):
    while stack and dic[n_list[stack[-1]]] < dic[n_list[i]]:
        result[stack.pop()] = n_list[i]
    stack.append(i)
print(*result)

백준 17298 오큰수와 매우 유사한 문제이다. (https://www.acmicpc.net/problem/17298)

이 문제는 등장한 횟수를 기준으로 수열을 구해야 하므로 dictionary를 통해 문제를 해결했다.

dictionary에 횟수를 저장하기 위해선 O(n) 나중에 횟수를 찾기 위해서는 O(1)이므로 시간 제한에 있어 걱정할 필요가 없다.

stack에 현재 숫자의 인덱스 값을 넣어가면서 진행. 현재 숫자의 횟수 보다 많은 횟수를 가진 수가 나오면 pop()하고 pop해서 나온 인덱스 값을 통해 result를 채워간다.