[Python] 백준, 2493(스택)

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

2493번: 탑

재밌는 문제! 근데 시간 초과가 자꾸 떠서 결국은 구글링.

 

# PYTHON CODE (1)

import sys
from collections import deque
 
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
stk1 = deque(s)
stk2 = deque()
answer = []
 
for _ in range(n - 1):
    a = stk1.pop()
    while stk1:
        if a <= stk1[-1]:
            break
        else:
            stk2.appendleft(stk1.pop())
 
    answer.append(len(stk1))
    stk1 = stk1 + stk2
    stk2 = deque([])
 
answer += [0]
for i in answer[::-1]:
    print(i, end=' ')

 

정답은 잘 나왔지만 시간 초과로 다른 방법을 찾아봤다.

 

 

# PYTHON CODE (2)

import sys
 
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
result = [0 for _ in range(n)]
stk = []
 
for i in range(n):
    a = s[i]
    while stk and s[stk[-1]] < a:
        stk.pop()
    if stk:
        result[i] = stk[-1] + 1
    stk.append(i)
 
print(' '.join(map(str, result)))

이 코드의 요지는 탑 왼쪽에 자기보다 낮은 높이의 탑은 존재할 필요가 없다는 것.

굳이 무리해서 탑의 순서를 구하지 않고, 인덱스에 1을 더해주며 깔끔히 마무리한다.

 

엄청 복잡한 문제는 아니어서 여기까지.