https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
입력 값의 뒤에서 부터 확인을 합니다.
만약 스택이 존재한다면, 스택의 마지막 부분이 현재 확인하고 있는 값보다 작지 않을 때 까지 pop 해줍니다.
그 후 현재 확인하고 있는 값을 스택에 넣어줍니다.
몇 번째 건물에서 레이저를 수신하는지 알아야하기 때문에 인덱스 정보도 같이 넣어줍니다.
입력 값들이 6 9 5 7 4 라면
처음에는 스택이 비어 있으므로 바로 스택에 넣어줍니다.
stack -> 4
그 다음 7을 보고, 스택에 4가 7보다 작으므로 4를 pop해준 후, 7을 스택에 넣습니다.
stack -> 7
5는 7보다 작으므로 바로 스택에 넣어줍니다.
stack -> 7 5
9를 확인할 때 스택에 있는 값이 모두 9보다 작으므로 모두 pop해준 후 9를 스택에 넣습니다.
stack -> 9
해당 과정을 반복합니다.
from sys import stdin
input = stdin.readline
n = int(input())
tower = list(map(int, input().split()))
stack = []
result = [0 for _ in range(n)]
for ii in range(len(tower)-1, -1, -1):
while stack and stack[-1]['height'] < tower[ii]:
result[stack.pop()['index']] = ii + 1
stack.append({
'height': tower[ii],
'index': ii
})
print(*result)