[스택] 백준 2493번 탑 with Python3

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

2493번: 탑

문제

 

내 풀이 -시간 초과-

import sys
from collections import deque

n = int(sys.stdin.readline())
stack = deque([])
ans = []
stack = deque(map(int, sys.stdin.readline().split()))

for i in range(1, n+1):
    teststack = deque(stack)

    for _ in range(i):

        ini = teststack.pop()

    for _ in range(n):
        index = len(teststack)
        if index == 0:
            ans.append(0)
            break
        initower = teststack.pop()
        if initower >= ini:
            ans.append(index)
            break
ans.reverse()

print(" ".join(map(str, ans)))

해설

시간초과를 해결하는 방법을 아직 찾지 못했다. 너무 for문이 많은거 같긴한데... 

일단 오른쪽에서부터 접근하는 방식으로 했다.

 

 

정답 풀이

# boj 2493 탑
# stack

if __name__ == "__main__":
    N = int(input())  # 탑의 개수
    top_list = list(map(int, input().split()))  # 탑 리스트
    stack = []
    answer = []
    
    #이 로직은 앞에서 뒤로 탐색해가며 해결한다.

    for i in range(N):
        while stack:  #스택이 비지 않은 동안.
        
            if stack[-1][1] > top_list[i]:  # 수신 가능한 상황 
            
                answer.append(stack[-1][0] + 1) #수신하는 탑의 index를 answ에 넣어준다
                
                break
                
            else:
                stack.pop() #
                
        if not stack:  # 스택이 비면 레이저를 수신할 탑이 없다.
            answer.append(0)
            
        stack.append([i, top_list[i]])  # 인덱스, 값

    print(" ".join(map(str, answer)))

출처:https://jjangsungwon.tistory.com/44

 

해석

구체적인 단계별 해석은 링크에 있다.

스택과 ans를 deque로 지정해주면 소요시간이 좀더 떨어진다. 100ms 정도