[BOJ] 백준 2493 탑 python

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

2493번: 탑

import sys
from collections import deque

count = int(sys.stdin.readline().rstrip())

numbers = list(map(int, sys.stdin.readline().rstrip().split()))

result = deque()
for _ in range(count):
    popped = numbers.pop()
    is_popped = False
    max_index = len(numbers) - 1
    for i in range(max_index + 1):
        if numbers[max_index - i] > popped:
            result.appendleft(max_index - i + 1)
            is_popped = True
            break
    if not is_popped:
        result.appendleft(0)

print(*result)

처음에 이렇게 풀고 시간 초과가 되었다.

나는 뒤에서부터 하나씩 pop해서 그걸 뒤에서부터 비교해가면서 index를 저장하려고 했는데

이렇게 하면 O(n^2) 가까이 되면서 시간 초과가 나는 것 같다.

 

어떻게 할지 고민해보다가..

중간에 작은 것들은 아예 빼버려도 괜찮다는 것을 알게 되었다.

별도의 스택을 이용해서 푸는 문제가 종종 나오기 때문에 앞으로 이런 문제가 나온다면 한 번쯤은 생각해보면 좋겠다.

탑의 높이는 100,000,000으로 나오기 때문에 처음 튜플은 그보다 1 더 큰 숫자를 넣어주었다.

통과한 코드는 아래와 같다. 

import sys
from collections import deque

count = int(sys.stdin.readline().rstrip())

numbers = list(map(int, sys.stdin.readline().rstrip().split()))

hash = deque()
hash.append((100000001, 0))

for i, number in enumerate(numbers):
    while hash[-1][0] < number:
        hash.pop()
    print(hash[-1][1], end=' ')
    hash.append((number, i + 1))