[백준][Python] 2493번 탑

2493번: 탑

 

코드

 

import sys
n = int(input())
tower = list(map(int,sys.stdin.readline().split()))
stack = []
ans = []

for i in range(n):
    while stack:
        if stack[-1][0] < tower[i]:
            stack.pop()
        else:
            break
           
    if stack:
        ans.append(stack[-1][1])
    else:
        ans.append(0)
    stack.append([tower[i],i+1])
for i in ans:
    print(i,end = " ")

 

설명

 

스택에 탑의 번호와 인덱스를 같이 추가해주었다.

탑 번호는 1부터 시작하기 때문에 스택에 인덱스 값을 넣어줄 때는 1씩 더해주어야 된다. 

만약 스택이 비어있지 않으면 while문을 통해 스택의 가장 마지막에 있는 탑 번호와 현재 탑 번호를 비교하여 현재 탑 번호가 더 크면 스택에 있는 것을 pop 해준다. 어차피 뒤에 있는 탑들의 신호는 탑 번호가 더 큰 현재 탑에서 수신하기 때문이다.

while문이 끝났을 때 스택이 비어있지 않으면 현재 탑의 신호를 수신할 수 있는 탑이 존재함을 의미한다. 따라서 그 탑의 인덱스 값인 stack[-1][1]을 ans 스택에 push 해준다.