[스택 / python] 백준 2493. 탑

문제

풀이

이 문제도 전형적인 스택 문제라고 느꼈다. 스택 문제들은 일반적으로 스택에 있는 것을 뽑아내서 기존에 주어진 리스트와 값을 비교, 조건에 맞으면 정답 리스트(ans)에 추가하고, 아니면 버리는 방식을 취한다. 이 문제에서는 더하여서, 정답 리스트를 0으로 초기화해서 탑에서 발사한 레이저가 막히지 않는 것을 기본으로 했다.

n = int(input()) # 탑의 수
li = list(map(int, input().split())) # 탑의 높이

ans = [0] * (n)
stack = []

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