[자료구조] 백준 2493번 탑 with Python

https://www.acmicpc.net/problem/2493
사실 아이디어는 바로 떠올랐지만 당연히 시간초과가 나는 코드란 걸 알았기에 무슨 방법이 있는지 고민을 해보았다.
키포인트는 중간에 우뚝 솟은 탑이 있다면 그 앞은 고려할 필요가 없다는 것이다.
하지만 그 뒤는 고려를 해줘야하는게 높이가 1 4 3 2 인 탑이 있다면 2은 4에 걸리는 것이 아니라 3에 걸리기 때문이다.
따라서 오른쪽부터 훑으면서 앞쪽의 탑들이 자신보다 낮으면 스택에서 빼고 높다면 그 탑이 자신이 발사하는 레이저에 걸리는 탑이 된다.(break)
그리고 자신도 그 뒤쪽 탑에겐 높을 수 있으므로 자신도 stack에 push 해야한다.
만약 앞쪽 탑들이 다 빠지고 자신밖에 스택에 없다면 자신보다 높은 탑이 없으므로 0을 append 해준다.

import sys

n = int(sys.stdin.readline().rstrip())

towers = list(map(int, sys.stdin.readline().rstrip().split()))

stack = [0]

answer = [0]

for i in range(1, len(towers)):

    for j in range(len(stack)-1, -1, -1):
        if towers[stack[j]] < towers[i]:
            stack.pop()
        else:
            break

    stack.append(i)

    if len(stack) == 1:
        answer.append(0)
    else:
        answer.append(stack[-2]+1)


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