역시나 바킹독 스택 강의 보고 푼 문제. 이걸 어떻게 스택으로 풀지 생각하느라 오래 걸렸다. 막상 이해하고 나니까 문제 푸는 시간은 얼마 걸리지 않았다.
(처음에 그냥 중첩 반복문으로 해결했는데 자료의 개수가 최대 500,000개가 주어져서 O(N^2)의 경우 너무 많은 연산이 발생하기 때문에 시간 초과가 났다.)
핵심은 탑 높이를 스택에 하나하나 쌓아나가는데, 신호를 수신할 가능성이 없는 탑(높이가 낮은 탑)은 미리 스택에서 제거해서 탐색할 자료의 개수를 줄여버리는 것이다.
인덱스를 출력해야 해서 어떻게 할지 고민이었는데 그냥 2차원 배열로 탑의 높이와 인덱스를 같이 저장했다.
n = int(input()) # 탑의 개수
a = input().split() # 탑 높이 배열
s = [] # 스택
for i in range(n) : # 탑 높이 배열의 수를 스택에 하나씩 추가하는 반복문
a[i] = int(a[i])
while s and s[-1][0] < a[i] : # 스택의 top이 추가하려는 탑 높이보다 작으면 다 pop
s.pop()
if s : # 자료가 남아 있으면 신호를 수신하는 탑이 있다는 뜻이므로
print(s[-1][1], end = ' ') # 스택 top의 인덱스 출력
else : # 자료가 남아 있지 않으면 신호를 수신할 탑이 없다는 뜻이므로
print(0, end = ' ') # 0 출력
s.append([a[i], i + 1]) # 탑의 높이과 인덱스를 스택에 저장
