[백준 2493번 ] 탑 (파이썬/python)

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

2493번: 탑

 

스택 자료구조를 이용해서 풀 수 있는 문제이다.

스택을 사용해서 필요없는 값들(작은 송신탑의 값들)을 pop( ) 해주면

효율적으로 필요한 길이의 송신탑만 탐색할 수 있다.

 

 

import sys
 
input = sys.stdin.readline
 
n = int(input())
arr = list(map(int, input().split()))
st = []
answer = ""
for i in range(n):
    while 1:
        # 스택에 값이 없으면 0출력, st에 append
        if not st:
            answer += "0 "
            st.append([arr[i], i + 1])
            break
 
        # 만약 st 맨 뒤의 값이 현재 arr[i] 값보다 작으면
        if arr[i] > st[-1][0]:
            st.pop()
            continue
        else:
            answer += str(st[-1][1]) + " "
            st.append([arr[i], i + 1])
            break
 
print(answer)