[백준] 1725번 : 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

전체코드(PyPy3)

from collections import deque
def max_area(arr):
    size = 0
    stack = deque()
    # 0번부터 끝까지 순회하면서 해당 높이에서 가장 큰 직사각형을 구한다.
    for i in range(len(arr)):   
        # stack 값이 들어가 있으면서 stack의 마지막 인덱스의 높이가 대상 히스토그램의 높이보다 높으면, 
        # 대상 히스토그램의 높이와 같거나 낮을때까지 계속 stack을 빼면서 직사각형의 면적을 구한다.
        while len(stack)!=0 and arr[stack[-1]] > arr[i] :
            # 마지막 히스토그램의 높이
            h = arr[stack.pop()]
            # 현재 인덱스의 값을 너비로 우선 초기화
            # 만일 stack에 값이 있다면 가장 i에서 가장 마지막 인덱스 값 -1의 값을 너비로 설정한다.
            w = i - stack[-1] -1 if len(stack)!=0 else i 
            # 저장한 직사각형보다 지금 구한 직사각형의 넓이가 크면 size에 저장한다.
            size = max(size,w*h)
        # stack의 마지막 인덱스 높이보다 크거나 같으면 stack에 추가한다.
        stack.append(i)
    # 모든 순회를 다 돌았으므로 스택을 하나씩 빼면서 넓이를 구한다.
    while len(stack)!=0:
        # 스택의 가장 마지막 인덱스의 히스토그램 높이
        h = arr[stack.pop()]
        # stack이 비어있을 경우 배열의 길이가 너비이므로 배열의 길이로 초기화
        # stack이 비어있지 않을경우 배열의 길이부터 stack의 마지막 인덱스 이전까지의 길이가 최대 너비이다.(현재 높이가 마지막 인덱스보다 크거나 같으므로)
        w = len(arr) - stack[-1] -1 if len(stack)!=0 else len(arr)
        # size보다 현재 구한 넓이가 크다면 size에 저장
        size = max(size,w*h)
    # 최대 직사각형의 넓이 반환
    return size

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
print(max_area(arr))

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.

오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

[ 참조 ]

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