백준 #17299 오등큰수

코드

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

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

for x in arr:
    if x not in dict:
        dict[x] = 1
    else:
        dict[x] += 1

answer = [-1] * n
stack = [0]

for i in range(n):
    while stack and dict[arr[stack[-1]]] < dict[arr[i]]:
        answer[stack.pop()] = arr[i]
    stack.append(i)

print(*answer)

풀이

오랜만에 스택 문제를 풀어보았다. 시간초과를 어떻게 해결해야할지 감이 안와서 구글링을 했따…

stack의 마지막 원소를 기준으로 오등큰수가 나오면 pop 해주고 answer에 저장해준다.

오등큰수를 못찾을 경우 stack에 인덱스를 그냥 넣어준다.

사실 코드를 보고도 이해가 잘 안가서 for문을 돌 때마다 answer 과 stack을 프린트해가며 확인해보았다.

쉬워보여서 도전했던 문제인데 시간을 꽤나 잡아먹었다 ㅠ

아직 갈길이 멀다..! 화이팅!