[백준알고리즘] 2493번: 탑 -Python

[백준알고리즘] 2493번: 탑 -Python

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

2493번: 탑

문제를 해결하기 위해서는 현재 탑의 바로 직전 탑의 높이만 알아야 하는 것이 아닌 자신이 도달할 수 있는 탑의 위치를 알기 위해서 어느 정도 이전 탑들의 정보가 필요하다.

 

하지만 탑의 개수도 많고, 높이의 범위도 넓기 때문에 이전에 나왔던 탑들을 모두 검사하는건 시간이 오래 걸릴 수밖에 없다.

 

그래서 필요없는 탑의 높이는 버리고, 필요한 탑의 높이만 유지하도록 작성했다.

 

필요 없는 탑의 높이란 오른쪽에 위치한 탑이 현재 탑의 위치보다 높은 것이다. 아래의 예와 같다.

주어진 탑의 위치가 다음과 같다고 하자
1 3 5 x
현재 탑의 높이인 x가 5보다 작다면 5에서 수신하기 때문에 1, 3의 높이 정보는 필요가 없다.

 

따라서 오른쪽으로 이동하면서 하나씩 탑을 볼 때 자신이 수신될 수 있는 탑의 위치를 찾을 때 이전의 탑의 높이가 현재 탑의 높이보다 작다면 버리면 되는 것이다.

 

import sys

n = int(sys.stdin.readline())
tower = list(map(int, sys.stdin.readline().split()))
stack = []
goto = [0] * n

for i in range(n):
    t = tower[i]
    while stack and tower[stack[-1]] < t:
        stack.pop()
    if stack:
        goto[i] = stack[-1] + 1
    stack.append(i)

print(' '.join(list(map(str, goto))))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다