[백준] 17299번(오등큰수)

백준 17299번

처음 제출한 코드(시간초과)

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

cnt = [0]*n
result = [-1]*n

for i in range(len(arr)):
  cnt[i] = arr.count(arr[i])

stack = [0]

for j in range(1, n):
  while stack and cnt[stack[-1]] < cnt[j]:
    result[stack.pop()] = arr[j]
  stack.append(j)

print(*result)

◼ 시간초과

• 아래 부분에서 시간초과가 발생했을 것으로 판단(실행시간 O(n**2))

for i in range(len(arr)):
  cnt[i] = arr.count(arr[i])

• 중복되는 원소의 개수를 count()를 사용해 배열해 저장하지 않고, 딕셔너리를 활용하는 코드로 수정

.

최종 제출 코드

n = int(input())
arr = list(map(int,input().split()))
result = [-1] * n
stack = [0]
arr_dict = {}
   
for i in range(n):
  if arr[i] in arr_dict:
    arr_dict[arr[i]] += 1
  else:
    arr_dict[arr[i]] = 1

for j in range(1, n):
  while (stack and arr_dict[arr[stack[-1]]] < arr_dict[arr[j]]):
    result[stack.pop()] = arr[j]
  stack.append(j)

print(*result)