[백준][Python] 2493번 탑 - 코팩

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

2493번: 탑

풀이

이중 for문을 사용하면 시간초과가 발생할 수 있다.

파이썬은 1초당 2000만 번의 연산이 가능하다.

그렇기에 n은 최대 500,000이 입력 값으로 주어질 수 있다. 500,000,000,000 -> 5천억 번의 횟수는
주어진 시간제한인 1.5초에 위배된다.

 

그렇기에 스택을 사용해서 시간 복잡도를 줄여야 한다.

아래의 코드의 시간 복잡도는 O(n)이기에 50만 번의 연산이 이루어진다.

 

코드

# 2493번 탑

n = int(input())
tower_h = list(map(int, input().split()))
ans = []
stack = []

for i in range(n):
    while stack:
        # 수신 받을 수 있는 탑 후보 > 송신하는 탑
        if stack[-1][1] > tower_h[i]:
            ans.append(stack[-1][0])
            break
        else:
            stack.pop()
    if not stack:
        ans.append(0)
    stack.append([i+1, tower_h[i]])

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

 

출력결과