import sys
class Tower:
def __init__(self, num, height):
self.num = num
self.height = height
def solution(n, towers):
answers = [0] * n
stack = []
for i in range(n):
towers[i] = Tower(i+1, towers[i])
stack.append(towers[-1])
for i in range(n-2, -1, -1):
while stack and stack[-1].height < towers[i].height:
tower = stack.pop()
answers[tower.num - 1] = i+1
stack.append(towers[i])
return answers
n = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))
answers = solution(n, towers)
for answer in answers:
print(answer, end=" ")
탑들을 역순회하면서 레이저를 송신하는 탑이 나타날 때까지
자료구조에 저장하여 관리해야 한다.
그럼 어떠한 자료구조가 적합할까?
바로 스택이다.
왜냐하면 스택에 들어왔다는 건 현재 스택에 있는 탑보다 높이가 낮다는 것이다.
그렇기 때문에 최근에 들어온 데이터(탑)부터 높이를 대조하여 처리해야 누락되는 데이터가 없을 것이다.
그래서 LIFO(Last In First Out)인 스택을 선택했다.