[엘리스] 히스토그램

히스토그램

가로의 길이가 1, 세로의 길이가 각각 다른 nn개의 판자들이 주어진다. 이 판자들은 아래 그림과 같이 모두 붙어있다.

직사각형 모양의 판자가 필요해 진 엘리스씨는, 이 붙어있는 판자들을 적당히 잘라내어 넓이가 가장 큰 직사각형을 얻고싶어 한다. 예를 들어, 위의 그림에서 얻을 수 있는 최대 넓이의 직사각형은 아래 그림과 같다.

n개 판자에 대한 정보가 주어질 때, 이를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 출력하는 프로그램을 작성하세요.

입력

첫째 줄에 n개의 판자의 높이가 차례대로 주어진다. (1≤n≤100,000) 첫 번째 숫자는 첫 번째 판자의 높이, 두 번째 숫자는 두 번째 판자의 높이, …, n번째 숫자는 n번째 판자의 높이를 나타낸다.

출력

주어진 판자를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 출력한다.

입력 예시

4 3 1 2 3 4 4 3 1

출력 예시

12

풀이 

• 분할정복법 : 직사각형의 최대 넓이는 3가지의 경우에서 나옴 
  • 중앙의 왼쪽에서 생긴 직사각형  
  • 중앙을 포함한 직사각형 
  • 중앙의 오른쪽에서 생긴 직사각형
• 중앙을 포함하지 않은 경우 : 분할 정복법 진행 
• 그렇지 않은 경우 : 왼쪽과 오른쪽으로 한칸씩 진행해가면서 더 큰 넓이 계산 
  • 여기서 더 큰 넓이는 높이가 큰 경우일 수 밖에 없음 !!! 

import sys

def getRect(heights) :
    '''
    n개의 판자의 높이가 주어질 때, 이를 적당히 잘라 얻을 수 있는 직사각형의 최대 넓이를 반환하는 함수를 작성하세요.
    '''
    n = len(heights)
	
    # 재귀 호출 종료 조건 : 크기가 1 이하이면, 가로 1 x 세로인 넓이 출력 
    if n <= 1 :
        return heights[0]

	# Pivot : mid값 기록 
    mid = n//2
	
    # left, right 각각 재귀호출 진행 
    left = getRect(heights[:mid])
    right = getRect(heights[mid:])

	# Point 기록 
    leftPtr = mid
    rightPtr = mid

	# 중앙 histogram 넓이 계산 
    curHeight = min(heights[leftPtr], heights[rightPtr])
    result = curHeight * (rightPtr - leftPtr + 1)

	# 왼쪽과 오른쪽으로 Point를 하나씩 옮겨가면서 넓이 계산 
    # 종료 조건 : 왼쪽 오른쪽 모두 확장할 공간이 없을 시 종료 
    while leftPtr-1 >= 0 or rightPtr+1 < n :
    	# 왼쪽과 오른쪽 중에 height가 높은 곳으로 point를 이동 
        leftHeight = heights[leftPtr-1] if leftPtr-1 >= 0 else -987987987987987
        rightHeight = heights[rightPtr+1] if rightPtr+1 < n else -987987987987987
        maxHeight = max(leftHeight, rightHeight)
	
        if leftHeight >= rightHeight :
            leftPtr -= 1
        else :
            rightPtr += 1

        curHeight = min(curHeight, maxHeight)
        
        # result를 기록해서 가장 max값만 저장
        result = max(result, curHeight * (rightPtr - leftPtr + 1))

    return max([result, left, right])

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(getRect(data))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn