[백준] 파이썬 2493번: 탑

 

 

# stack
# 탑 개수만큼 반복
# 레이저가 발사되는 탑의 이전 탑이 더 높거나 같아야 수신 가능.
# 현재 탑과 이전 요소들을 비교해서 현재 탑보다 낮다면 건너뛰기.
# 높거나 같다면 해당 요소 인덱스를 결과에 추가.

n = int(input())
towers = list(enumerate(map(int, input().split()))) # 인덱스 + 탑높이
result = [0 for _ in range(n)] # 결과 배열
stack = [] # 왼쪽 탑과 비교해줄 stack

for idx, height in towers:
    while stack: # stack에 값이 있을때. 맨 왼쪽은 수신이 안되니까 그냥 넘어감.
        top_idx, top_height = stack[-1] # 현재 탑에서 왼쪽에 있는 탑
        if top_height >= height: # 높이를 비교해서 왼쪽 탑이 같거나 높으면 = 수신이 된다면
            result[idx] = top_idx + 1 # 결과배열의 일치하는 인덱스에 번호를 추가
            break
        else:
            stack.pop() # 일치하지 않으면 그 다음 탑(왼왼쪽..)을 확인할 수 있게 스택에서 제거
    stack.append((idx, height)) # stack에 현재 탑을 추가 

print(*result)

 

 

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

2493번: 탑