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

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

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

제한시간: 1초
메모리 제한: 256 MB

문제

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

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

입력

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

출력

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

예제 입력 1

 

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

 

예제 출력 1

8

4000

---

어렵다 너무 어려워.

(해설 링크)를 보고 이해...해보도록 하자

---

정답 코드

import sys 


if __name__=="__main__":
    while True:
        infos = list(map(int, sys.stdin.readline().split()))
        if infos[0] == 0:
            break

        N=infos[0]
        stack = []
        max_area = 0
        # 처음 바부터 끝 바까지 확인
        for i, height in enumerate(infos):
            if i == 0:  # 첫 번째 i는 막대기의 개수를 의미하므로 넘어갑니다.
                continue

            # 2단계
            # stack에 마지막으로 들어간 막대 보다 짧은 막대를 만나면 
            # 스택에 들어있는 막대의 넓이를 계산한다. (2단계와 유사)
            if stack and stack[-1][1]>height:
                while stack:   # stack에 쌓인 막대들을 모두 보면서 최대값인 넓이를 찾음
                    stack_i,stack_h=stack.pop()
                    width=1
                    if stack:               # pop으로 가장 위에꺼 뺐는데 아직 저장한 stack이 있으면
                        width=stack[-1][0]+1
                    area=(i-width)*stack_h      # 넓이를 구함
                    max_area=max(area,max_area) # 최대값 갱신
                    if not stack or stack[-1][1] <= height: # stack이 비었거나 현재 바 높이가 더 크면
                        break

            # 1단계
            # 스텍이 비어있거나 스텍 마지막 막대보다 현재 막대 높이가 크거나 같으면 
            # 스텍에는 바가 오름차순으로 들어간다. 유일하게 stack에 넣을때
            if not stack or stack[-1][1]<=height:
                stack.append([i, height])  # 스택에 현재 막대기를 추가합니다.

        # 3단계
        # 반복이 종료되고, 스텍에 남은 막대기가 있으면 직사각형 넓이를 계산한다 
        while stack:
            stack_i,stack_h=stack.pop()
            width=1
            if stack:
                width=stack[-1][0]+1
            area = (N+1-width)*stack_h
            max_area=max(area,max_area) # 최대값 갱신

        # 최대 직사각형 넓이를 출력합니다.
        print(max_area)

이걸 어케 풀어....

---