import sys
from collections import defaultdict
n = int(input())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
d = defaultdict(int)
answer = [0]
max_val = arr[0]
stack = [(1, max_val)]
for tower, height in enumerate(arr[1:], 2):
if height >= max_val:
max_val = height
stack.clear()
stack.append((tower, height))
else:
receive_tower_idx = len(stack) - 1
while stack and stack[-1][1] <= height:
stack.pop()
receive_tower_idx -= 1
stack.append((tower, height))
d[tower] = stack[receive_tower_idx][0]
for i in range(1, n + 1):
print(d[i], end=' ')
import sys
n = int(sys.stdin.readline().rstrip())
top = list(map(int, sys.stdin.readline().rstrip().split()))
ans = [0]
stack = [0]
for i in range(1, len(top)):
while stack and top[stack[-1]] < top[i]:
stack.pop()
if not stack:
stack.append(i)
ans.append(0)
else:
ans.append(stack[-1]+1)
stack.append(i)
print(' '.join(map(str, ans)))
stack 유형의 문제에서 while 문과 stack의 마지막 항을 비교하는 방식은 자주 사용된다.
receive_tower_idx = len(stack)-1
를 어떤 방식으로 사용했는지 기억하자.
++
다시 풀어봤다. 7개월 전보다는 풀이가 나아졌다.