[백준] 6549 히스토그램에서 가장 큰 직사각형 - 파이썬

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

---

해결 방법

 

처음 접근한 방법은 dp를 이용해서 풀어보려고 했습니다. 첫번째 사각형을 첫번째 원소로 놓고 진행하며 현재 사각형 높이가 이전 사각형 높이보가 증가한 경우, 감소한 경우, 증감의 크기가 1인 경우와 아닌 경우로 나눠서 머리를 싸매면서 풀었는데 결국 해결을 못했습니다 ㅜㅜ 반례에 늪에 빠지고 말았습니다.....

 

그래서 풀이를 참조하여보니 세그먼트 트리로 푸는 방법 한 가지와, 스택을 이용한 풀이 한 가지가 있었습니다. 저는 dp로 풀려고 접근했을 때 부터 스택을 이용한 방식처럼 풀려고 했기 때문에 스택을 이용한 풀이가 더 빨리 와닿았습니다.

 

문제의 예시에서 Input은 7 2 1 4 5 1 3 3 이고 Output은 8입니다.

 

이 문제에서 중요한 풀이방법은 현재 사각형 높이가 이전 사각형 높이보다 작을 때만 계산해주면 되는 것입니다.

* 여기서 스택에 인덱스를 넣는 이유는 사각형 넓이를 계산할 때 밑변의 길이로 사용할 수 있기 때문입니다.

1. 1부터 N까지 반복합니다. 

2. 스택에 원소가 존재하고, 다음 사각형의 높이가 감소하는 경우 스택에서 pop합니다. pop한 데이터: ind(인덱스)
2-1) pop하고 난 후 스택이 비어있으면,  밑변 = i (현재 인덱스만큼이 밑변의 길이)
2-2) pop하고 난 후 스택에 원소가 있으면, 밑변 = i - stack[-1] - 1
        stack[-1]: 내가 계산하려고 하는 사각형의 인덱스
        i - stack[-1] -1: 현재 인덱스에서 계산하려고 하는 사각형까지의 거리

3. 현재까지 넓이의 최대값을 갱신해줍니다. ans = max(ans, width * data[ind])
    data[ind]: 해당 사각형의 높이

4. 스택에 현재 인덱스를 추가합니다.

5. 1 ~ 4를 반복하며 N까지 검사했을 때, 스택에 원소가 남아있다면 마지막 사각형까지 검사를 다 했으므로 2번 과정을 밑변의 길이를 i가 아닌 N을 기준으로 해서 계산해준다.

 

   
import sys
from collections import deque

input = sys.stdin.readline


while True:
    data = list(map(int, input().split()))

    if len(data) == 1 and data[0] == 0:
        break
    
    N = data.pop(0)
    d = deque()
    ans = 0
    for i in range(N):
        while len(d) > 0 and data[d[-1]] > data[i]:
            tmp = d.pop()

            width = 0
            if len(d) == 0:
                width = i
            
            else:
                width = i - d[-1] - 1
            
            ans = max(ans, width * data[tmp])

        d.append(i)
    
    while len(d) > 0:
        tmp = d.pop()

        width = 0
        if len(d) == 0:
            width = N
            
        else:
            width = N - d[-1] - 1
        
        
        ans = max(ans, width * data[tmp])

    print(ans)