172. 6549 (히스토그램에서 가장 큰 직사각형) - 파이썬

from collections import deque
import sys
input = sys.stdin.readline

while True:
    h = list(map(int, input().split()))
    n = h.pop(0)
    if n == 0:
        break
    stack = []
    result = 0

    for i in range(n):
        while len(stack) != 0 and h[stack[-1]] > h[i]:
            tmp = stack.pop()

            if len(stack) == 0:
                w = i
            else:
                w = i - stack[-1] - 1
            result = max(result, w * h[tmp])
        stack.append(i)


    while len(stack) != 0:
        tmp = stack.pop()

        if len(stack) == 0:
            w = n
        else:
            w = n - stack[-1] - 1
        result = max(result, w * h[tmp])
    print(result)

문제요약

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형으로 직사각형이 가장 큰 값을 구하라.

설명

이 문제는 스택, 분할정복, 세그먼트 트리등을 이용하여 풀 수 있다.

스택이 제일 간단하고 이해하기 쉽기 때문에 스택을 이용하여 풀이를 진행하겠다.

 

아래 사이트를 참고했다.

https://hooongs.tistory.com/330

[백준6549번] 히스토그램에서 가장 큰 직사각형 / Python3

다음과 같은 값이 주어졌다.

3번째, 4번째를 이용해서 만든 직사각형 크기가 8로 가장 큰 직사각형에 해당한다.

이를 스택을 이용해서 풀어야 한다.

 

1차

        while len(stack) != 0 and h[stack[-1]] > h[i]:
            tmp = stack.pop()

            if len(stack) == 0:
                w = i
            else:
                w = i - stack[-1] - 1
            result = max(result, w * h[tmp])
        stack.append(i)

(1) 현재 i 는 0

먼저 스택에 0번째 인덱스에 해당하는 2를 넣는다.

 

(2) 현재 i 는 1

스택에 들어있던 '2'가 새로 들어온 '1'보다 크기 때문에 2를 빼고 result 후보군에 넣게 된다.

이후 스택이 비어있으므로 1을 집어 넣는다.

 

(3) 현재 i 는 2

4가 1보다 크기 때문에 stack에 값을 넣고 다음으로 넘어간다.

 

(4) 현재 i 는 3

5가 4보다 크기 때문에 stack에 값을 넣고 다음으로 넘어간다.

 

(5) 현재 i는 4

 

4번째의 값은 1이다.

따라서 2번째, 3번째는 pop을 통해 값을 빼고 계산을 진행해야한다.

계산된 값과 그전에 있던 result를 비교해서 둘 중 더 큰 값을 result에 저장한다.

 

(6) 현재 i 는 5

3이 1보다 크기 때문에 stack에 값을 넣고 넘어간다.

 

(7) 현재 i 는 6

3이 1보다 크기 때문에 stack에 값을 넣고 넘어간다.

 

2차

    while len(stack) != 0:
        tmp = stack.pop()

        if len(stack) == 0:
            w = n
        else:
            w = n - stack[-1] - 1
        result = max(result, w * h[tmp])

stack 에 넣는것은 끝났다 하지만 아직 스택에 값이 있으므로 2차에서는 스택을 비우는 작업을 통해서 result가 더 큰 것이 있다면 그 값을 result에 넣을 것이다.

 

계산을 진행해도 8이 가장 크다는 것을 알 수 있고 그 8이 출력값이 되는 것이다.