[Python] 백준 6549

교훈 : 플래라고 겁먹지 말자

 

 

 

 

 

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에 들어가는 직사각형의 넓이