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

 

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

 

문제

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

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

입력

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

출력

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

예제 입력  7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

예제 출력  8 4000

 

풀이

 

분할 정복과 스택 두 가지 방법으로 풀 수 있는 문제인데, 분할 정복 챕터에 있으니 분할 정복으로 풀었다.

 

분할 정복으로 풀 때 문제가 한 가지 있었는데, 바로 세그먼트 트리(구간 트리)를 알아야 한다는 것이다.

 

사실 분할 정복으로 구현하는 것보다 세그먼트 트리를 공부하는 데 쏟은 시간이 긴 것 같다.

 

감을 잡기 어려워서, 여기저기 검색의 도움을 받았다.

 

기본적인 원리는 이렇다.

 

1. 현재 주어진 히스토그램의 가장 낮은 높이 x 히스토그램의 길이를 구한다.
2. 가장 낮은 블럭을 기준으로 양분할 한다.
3. 3가지 넓이 중 가장 큰 것을 리턴

 

여기서 세그먼트 트리가 필요한 이유가 나온다.

 

히스토그램을 분할할 때마다 해당 히스토그램에서 가장 낮은 높이를 구해야 하는데

 

히스토그램의 최대 길이가 100,000이기 때문에 그냥 min을 쓸 경우 시간 초과에 걸리게 된다.

 

따라서 구간의 최솟값을 O(logN)의 시간복잡도로 구할 수 있는 세그먼트 트리를 활용해야 한다.

 

import math, sys
input = sys.stdin.readline

# 아래의 설정을 해주지 않으면 최대 재귀 제한에 걸려 런타임 오류가 생긴다.
sys.setrecursionlimit(10**6)

# 세그먼트 트리 생성
def init(arr,tree,node,start,end):
    if start == end:
        tree[node-1] = start
    else:
        mid = (start+end)//2
        init(arr,tree,node*2,start,mid)
        init(arr,tree,node*2+1,mid+1,end)
        # node-1은 부모, node*2-1과 node*2는 각각 왼쪽, 오른쪽 자식노드를 의미
        
        if arr[tree[node*2-1]] < arr[tree[node*2]]:
            tree[node-1] = tree[node*2-1]
        else:
            tree[node-1] = tree[node*2]
            # 부모 노드에 더 작은 자식 노드를 입력
            
# 구간 최솟값을 찾아주는 쿼리 함수
def query(arr,tree,node,start,end,x,y):
    # 주어진 범위가 전체 범위를 벗어난 경우
    if x > end or y < start:
        return -1
    # 주어진 범위가 전체 범위 안에 포함되는 경우
    if start >= x and end <= y:
        return tree[node-1]

    mid = (start+end)//2
    left = query(arr,tree,node*2,start,mid,x,y)
    right = query(arr,tree,node*2+1,mid+1,end,x,y)

    # 한쪽 노드가 범위를 벗어난 경우 자연스럽게 반대쪽 노드가 선택됨
    if left == -1:
        return right
    elif right == -1:
        return left
    else:
        # 더 작은 값의 인덱스 선택
        if arr[left] >= arr[right]:
            return right
        else:
            return left

def dac(start,end):
    # 해당 구간 범위의 최솟값 인덱스를 구함
    index = query(arr,tree,1,0,len(arr)-1,start,end)
    
    # 단일 블럭인 경우
    if abs(end-start)==0:
        return arr[index]
    
    # v1 = 가장 낮은 블럭의 높이 * 히스토그램의 길이
    v1,v2,v3 = arr[index] * (end-start+1),0,0
    
    # 범위를 벗어나지 않는 경우 분할
    if index-1 >= start:
        v2 = dac(start,index-1)
    if index+1 <= end:
        v3 = dac(index+1,end)
        
    return max(v1,v2,v3)

while(True):
    temp = list(map(int,input().split()))
    if temp[0] == 0:
        break
    
    n = temp[0]
    arr = temp[1:]
    tree = [0]*(pow(2,math.ceil(math.log(len(arr),2))+1)-1)
    # 편하게 n*4를 해도 되지만, 최적 길이로 생성하는 방법은 위와 같다

    init(arr,tree,1,0,len(arr)-1)
    print(dac(0,len(arr)-1))