[백준/BOJ] platinum5 - 6549번 히스토그램에서 가장 큰 직사각형 (Python)

▶6549 - 히스토그램에서 가장 큰 직사각형

▶문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

 

▶입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

 

 

▶출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

728x90

▶풀이

말로 잘 설명할 자신이 없다.

나도 그림을 그려가면서 이해했기 때문에...

​

설명하면 stack을 하나 만들고 각각의 인자로 [높이, a]

a는 stack 마지막 값의 높이가 현재의 높이보다 작다면 i의 값을 집어넣어 주면 된다

​

이해가 되지 않는다면 구글링을 해보는 것을 추천한다...

그림을 보면 바로 이해가 갈 것이다.

​

        while stack and stack[-1][0] >= rect[i]:
            h, index = stack.pop()
            size = h * (i-index)
            max_s = max(max_s, size)

 

어쨌든 스택을 빼주면서 size를 구해주고, max_s와 비교해서 큰 값을 max_s에 넣어준다.

진짜 그림을 보면 바로 이해가 갈 거다...

​

나는 이해를 했고, 글을 못 적을 뿐이고그림을 못 그릴 뿐이다...ㅎㅎ​

누군가 이걸 본다면 코드만 참고하고, 구글링 해서 꼭 그림을 보면 좋겠다.

​

def maxsize():
    max_s = 0
    stack = []

    for i in range(n):
        index = i
        while stack and stack[-1][0] >= rect[i]:
            h, index = stack.pop()
            size = h * (i-index)
            max_s = max(max_s, size)
        stack.append([rect[i], index])

    for h, left in stack:
        max_s = max(max_s, (n-left)*h)
    return max_s


result = []
while True:
    n, *rect = map(int, input().split())

    if n == 0:
        break
    result.append(maxsize())

for i in result:
    print(i)