문제 링크

설계

제일 중요한 것은 "스택을 떠올릴 수 있느냐" 라고 생각한다.

나도 처음에 바로 떠올리지 못 해서 약 1시간 정도 감을 못 잡았던 것 같다.

그렇다면 어떻게 이 문제를 스택으로 풀 수 있을지 그림으로 설명해보도록 하겠다.

스택 동작 구조

"입출력 예제2"

1. 스택의 길이가 곧 쳐다보는 신선의 수 따라서, 이를 정답 배열에 추가한다.

2. 현재 산봉우리 높이보다 이하값을 모두 팝한다.

3. 현재 산봉우리 높이를 스택에 추가한다.

전체 코드

if __name__ == '__main__':
	n = int(input())
	height = list(map(int,input().split()))
	stack = [height[0]]
	answer = [0]
	for i in range(1,n):
		answer.append(len(stack))
		while stack and stack[-1] <= height[i]:
			stack.pop()
		stack.append(height[i])
	print(*answer)