[python] 백준 2493번 탑

백준 2493번 탑

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

문제

풀이

인풋받기

import sys
input = sys.stdin.readline
n = int(input())
towers = list(map(int, input().split()))

시간초과를 예상하고도 푼 방법

answer = []
stack = []

for i in range(n):
    if stack == []:
        answer.append(0)

    else:
        if nlist[i] > max(stack):
            answer.append(0)
        else:
            for j in range(len(stack)-1, -1, -1):
                if stack[j] >= nlist[i]:
                    answer.append(j+1)
                    break

    stack.append(nlist[i])

print(*answer)

이 문제는 스택을 이용해야만 시간초과에서 벗어날 수 있다.
그럼 스택을 어떻게 이용할까?
스택의 탑이 현재 탑보다 낮으면 스택에서 제거.

stack = []
answer = [0] * n

for i in range(n):

    while stack:
        if stack[-1][1] > towers[i]:
            answer[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()

    stack.append((i, towers[i]))
print(*answer)

예를 들어보자.
[6, 9, 5, 7, 4]

• 탑 1: stack = [(0, 6)], answer = [0, 0, 0, 0, 0]
• 탑 2: stack = [(1, 9)], answer = [0, 0, 0, 0, 0]
• 탑 3: stack = [(1, 9), (2, 5)], answer = [0, 0, 2, 0, 0]
• 탑 4: stack = [(1, 9), (3, 7)], answer = [0, 0, 2, 2, 0]
• 탑 5: stack = [(1, 9), (3, 7), (4, 4)], answer = [0, 0, 2, 2, 4]

그리고 일단 answer에다가 [0,0,0,0,0]을 넣고 시작하는 게 훨씬 편한 것 같다.

📌 주의

스택과 친해지기...