[Python] 백준 #2493 탑

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

2493번: 탑

[ 자료구조 ]

스택

 

[ 접근 방법 ]

완전 탐색으로 구현하면 시간초과나는 문제이다.

처음에 완전 탐색으로 접근해서, 뒤에부터 앞에를 하나씩 탐색하니 시간초과가 발생하였다.

해결한 방법은,

스택을 이용하여 맨 앞부터 그 전에 스택이 담긴 원소들과 비교를한다.

(1) 스택이 비어있는 경우

= 수신 받을 탑이 없다는것 (자신보다 높은 탑이 없다는 것)

 

(2) 스택이 비어있지 않은 경우

현재의 높이와 스택[-1] 의 높이를 비교해서 현재 높이보다 낮으면 pop해준다.

현재 높이 보다 높으면 수신 받을 수 있으므로 결과값에 저장한다.

 

[ 코드 ] O(N) 676ms

from collections import deque
import sys

n = int(sys.stdin.readline().strip())
List = list(map(int, sys.stdin.readline().strip().split()))
stack = deque()
result = []

for i in range(len(List)):
    while stack:
        if stack[-1][0] > List[i] : #나보다 큰 애 존재
            result.append(stack[-1][1])
            break
        else:
            stack.pop()

    if not stack: #스택 비어있음
        result.append(0)

    stack.append((List[i], i + 1))

result = ' '.join(map(str, result))

print(result)