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

✅문제 - 히스토그램에서 가장 큰 직사각형 (6549번)

---

 

✅필요 알고리즘 개념 - (분할 합 / 스택)

---

🔵 풀이 1 - 스택을 이용한 풀이

1. stack에 높이가 담겨진 num_list의 idx를 push 하다가 num_list[stack[-1]] 의 값이 num_list[idx] 보다 큰 경우 stack을 pop하여 tmp에 저장한다.
(이 때 num_list[stack[-1]] 의 값이 num_list[idx]의 값 이하가 될 때까지 pop을 진행한다. )
--> 이 말 뜻은 pop하여 얻은 tmp 값은 stack에 남아 있는 값들보다 크다는 것을 의미한다.

2. 직사각형의 너비와 높이를 구한다.
높이는 num_list[tmp]이 된다. ( 우리가 push 하는 것은 높이가 아니라 높이가 들어있는 idx 값이기 때문이다. )
❗❗❗너비를 구하는 것이 어려다.
tmp 값의 의미를 잘 알아야 하는데 tmp 값은 stack에 들어있는 값들 중 최대 값이 된다.
그러므로 tmp는 stack의 맨 위( [-1] ) 값보다 크다.
그러므로 width = idx - stack[-1] -1 이 된다. ( -1 은 index와 길이간의 차이로 인해 발생하는 오차를 없애기 위한 값으로 idx - stack[-1]을 이해하는 것이 중요하다.)

✅코드

---

import sys

input = sys.stdin.readline

while True:
    nlt = list(map(int,input().rstrip().split()))
    number = nlt.pop(0)

    if number == 0:
        break

    answer = 0
    stack = []

    for idx in range(number):
        while len(stack) != 0 and nlt[stack[-1]] > nlt[idx]:
            tmp = stack.pop()
            
            if len(stack) == 0:
                width = idx
            else:
                width = idx - stack[-1] - 1
            
            answer = max(answer, width*nlt[tmp])
        stack.append(idx)
    
    while len(stack) != 0:
            tmp = stack.pop()
            
            if len(stack) == 0:
                width = number
            else:
                width = number - stack[-1] - 1
            
            answer = max(answer, width*nlt[tmp])
    
    print(answer)