[Python/파이썬] 백준 2493번 탑

https://www.acmicpc.net/problem/2493

 

코드

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

stack = []
ans = [0]*n

for i in range(n):
    while stack and stack[-1][0] <= towers[i]:
        stack.pop()
    ans[i] = (stack[-1][1]+1 if stack else 0)
    stack.append((towers[i], i))
print(*ans)

 

for문을 i까지 돌았을 때 stack에는 towers[i-1]와 그보다 큰 타워들만 저장되어 있다. i번째 타워는 스택에서 자신보다 작은 타워는 다 pop하고 스택의 top, 즉 자신보다 큰 타워의 인덱스+1을 ans[i]에 저장하면 된다.

 

문제의 테스트케이스로 예를 들자면,

위의 예시에서는 높이가 4인 5번째 타워까지 왔을 때 스택에 저장된 타워는 바로 이전 타워인 4번과 그보다 더 큰 타워인 2번이다.

그러므로 5번째 타워는 자신보다 큰 4번 타워의 인덱스를 저장하면 된다.