백준 2493 - python풀이 (스택)

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

2493번: 탑

 

간단해 보이지만 간단히 완전탐색으로 풀면 시간복잡도가 최악의 경우 n! 이 되기때문에 스택을 써야한다

 

또한 인덱스를 저장해야하기 때문에 스택안에 리스트가 들어가는 구조로 풀어줘야 한다.

 

 

import sys
N=int(sys.stdin.readline())
tower=list(map(int,sys.stdin.readline().split()))

stack=[]
ans=[]

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