백준 2493 [탑] 파이썬

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

2493번: 탑

# 백준 2493 오답
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
dp = [0]*(n)

for i in range(n):
    for j in range(i+1, n):
        if lst[i] < lst[j]:
            break
        elif lst[i] == lst[j]:
            dp[j] = (i+1)
            break
        else:
            dp[j] = (i+1)

print(*dp)

맨 처음에는 단순한 반복문 구현으로 O(N^2)의 시간 복잡도로 해결하려고 하였다. --> 시간초과

# 백준 2493
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
answer = [0]*(n)
stack = []
for i in range(len(lst)):
    if not stack:
        stack.append([lst[i], i, 0])
    else:
        if stack[-1][0] <= lst[i]:
            while stack and stack[-1][0] <= lst[i]:
                val = stack.pop()
                answer[val[1]] = val[2]
        if stack:
            stack.append([lst[i], i, stack[-1][1]+1])
        else:
            stack.append([lst[i], i, 0])

while stack:
    val = stack.pop()
    answer[val[1]] = val[2]
print(*answer)

잘 풀리지 않아 문제의 알고리즘이 스택인 것을 파악하고, 스택으로 문제를 해결하였다.