[백준/Python] 탑

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

2493번: 탑

[ 실패 코드 ] - 시간 초과

시간 초과의 이유를 살펴보니 index, slicing 을 사용하면 시간 초과가 났다고 한다. 나는 둘 다 사용하지 않았지만 시간초과가 났다. 뒤에서부터 비교 -> 앞에서부터 비교로 바꾸고 코드 구성을 바꿔줬더니 통과하였다. 시간초과...해결하기 너무 어렵다....

n = int(input())
towers = list(map(int, input().split()))
stack = [(t, i+1) for i, t in enumerate(towers)]
answer = []

while stack:
    now = stack.pop()
    for i in range(len(stack)-1, -1, -1):
        next, idx = stack[i]
        if now[0] <= next:
            answer.append(idx)
            break
    else:
        answer.append(0)

print(*answer[::-1])

 

[ 성공 코드 ] 

n = int(input())
towers = list(map(int, input().split()))
stack = []
answer = [0] * n
 
for i in range(n):
    while stack:
        if stack[-1][0] > towers[i]:
            answer[i] = stack[-1][1] + 1
            break
        else:
            stack.pop()
    stack.append((towers[i], i))
 
print(*answer)

1. 답을 담는 리스트 answer 를 생성하고 0으로 초기화한다.

2. 모든 타워를 앞에서부터 비교하는 과정을 반복한다. 

    2-1. stack에 값이 없으면 stack에 현재 타워를 추가한다.

    2-2. stack에 값이 있으면 이전 타워를 하나씩 가져와 비교한다.

    2-3. 이전 타워가 현재 타워보다 크다면 신호를 수신할 수 있는 것이므로 답을 이전 타워의 번호로 바꾼다.(번호가 1부터 시작하므로 +1을 해주는 것!)

    2-4. 이전 타워가 현재 타워보다 크지 않다면 스택에서 이전 타워를 없앤다.

3. 답을 출력한다.