탑 (2493번) - 백준 (BOJ)

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

2493번: 탑

 

 

백준 - 탑 (2493번)

 

난이도 : Gold 5

알고리즘 : Stack (스택)

Time Complexity : O( N )

 

 

if __name__ == '__main__':
    N = int(input())
    stack = [(0, 100_000_001)]
    rs = [0] * N
    for i, h in enumerate(map(int, input().split())):
        while stack[-1][1] < h:
            stack.pop()
        rs[i] = stack[-1][0]
        stack.append((i+1, h))
    print(*rs)

 

 

스택으로 해결 가능한 문제이다.

 

현재 탑 ( i ) 의 높이 ( h ) 를 스택에 넣기 전에,

스택 안에 존재하는 ( h ) 보다 작은 값들을 제거해준다.

 

모두 제거하고 난 뒤 가장 최근에 남은 탑이,

현재 탑에서 쏜 레이저를 수신하는 탑이다.

이를 rs[i] 에 기록해둔다.

 

이후 현재 탑의 인덱스와 높이 ( i+1, h ) 를 스택에 넣어준다.