교훈 : 플래라고 겁먹지 말자
stack을 이용해서 풀었다
stack 삽입 : index와 높이(h)
원리 : 현재 index보다 stack에 있는 index(나보다 왼쪽)의 h가 더 크면 현재 index의 h값으로 왼쪽도 포함할 수 있다.
더보기
여기서 오른쪽의 높이(2) 로 왼쪽을 포함하여 넓이가 4가 될 수 있다.
이 원리를 이용해 stack으로 풀 수 있었다!
import sys
while True:
#마지막에 stack에 있는 값을들 다 꺼내기 위해 마지막 h값은 0
h = list(map(int, sys.stdin.readline().split())) + [0]
if h[0] == 0:
break
n = h[0]
stack = [(1,h[1])]
res = 0
for i in range(2,n+2):
w = i
#나보다 stack에 있는 h가 더 높으면 꺼내서 (나의 높이 * 너비)
while stack and stack[-1][1] > h[i]:
w, hi = stack.pop()
res = max(res, (i-w)*hi)
stack.append((w, h[i]))
print(res)
예제로 실행했을 때 res에 들어가는 직사각형의 넓이
'Algorithm > Solution' 카테고리의 다른 글
[Python] 백준 2089 (0) | 2021.03.04 |
---|---|
[Python] 백준 1442 (0) | 2021.02.25 |
[Python] 백준 6549 (0) | 2021.02.20 |
[Python] 백준 2606 (0) | 2020.09.01 |
[Python] 백준 1260 (0) | 2020.08.27 |
[Python] 백준 2231 (0) | 2020.05.03 |