[백준] 6549 히스토그램에서 가장 큰 직사각형, python

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

 

 

 

 

 

주어진 히스토그램 내에서 가장 큰 직사각형의 넓이를 구하는 문제이다.

이 문제는 세그먼트 트리와 분할정복을 통해 \(O(nlogn)\) 으로 푸는 방법과

단조 스택(monotonic stack)을 사용해 \(O(n)\)의 시간 복잡도로 풀 수 있다.

 

 

 

세그먼트 트리와 분할정복을 사용한 풀이

 

세그먼트 트리, python

세그먼트 트리, python

 

 

 

 

위 그림에서 구간 별 최소 높이 막대의 인덱스를 구하기 위해 세그먼트 트리를 생성하고 초기화한다.

 

 

 

 

 

세그먼트 트리에서 부모노드는 자식노드 중 높이가 낮은 막대의 인덱스를 넣어주면 된다.

0번 막대의 높이는 2이고, 1번 막대의 높이가 1이므로 부모노드에는 둘 중 낮은 막대의 인덱스인 1을 넣어주면 된다.

 

 

 

 

 

 

이렇게 세그먼트 트리를 초기화해준다.

 

구한 세그먼트 트리를 통해 구간 내 가장 낮은 높이를 가진 막대의 인덱스를 기준으로 왼쪽 오른쪽 구간을 나누어 가면서 재귀로 최대 넓이를 업데이트해주면 된다.

 

 

 

 

0,6구간에서 가장 작은 높이를 가진 막대의 인덱스를 세그먼트 트리에서 구한다. query(0,6) = 4이다.

4번 막대를 기준으로 왼쪽과 오른쪽을 나눈다.

높이는 4번 막대의 높이(1), 너비는 구간(6 - 0 = 6)의 직사각형 area의 넓이( 1* 6 = 6 )와

4번 막대를 기준으로 왼쪽, 오른쪽 구간에서 재귀로 반복해 주며 구한 area값의 최댓값을 구해준다.

 

 

 

 

마찬가지로 구간 내 가장 작은 높이를 가진 막대의 인덱스를 기준으로 양쪽으로 나눠서 반복해 준다.

 

 

 

 

import sys
sys.setrecursionlimit(10**6)

def solve(h):
    n = len(h)

    #세그먼트 트리 생성 및 초기화
    size = 1
    while size<n:
        size*=2
    segtree = [0]*(2*size)
    for i in range(n):
        segtree[i+size] = i
    for i in range(size-1,0,-1):
        left, right = segtree[2*i], segtree[2*i+1]
        # 높이가 같거나 낮은 막대의 인덱스를 저장
        segtree[i] = left if h[left]<h[right] else right

    # 인덱스 l,r 사이에서 높이가 가장 낮은 막대의 인덱스를 구함
    def query(l,r):
        l = size+l
        r = size+r
        index = -1
        while l<=r:
            if l%2==1:
                if index==-1 or h[segtree[l]] < h[index]:
                    index = segtree[l]
                l += 1
            if r%2==0:
                if index==-1 or h[segtree[r]] < h[index]:
                    index = segtree[r]
                r -= 1
            l//=2
            r//=2
        return index

    # 구간 l과 r을 세그먼트 트리에서 구한 l과 r사이의 최소 높이 막대의 인덱스를 기준으로 
    # 왼쪽 오른쪽 구간을 나누어 재귀로 넓이의 최댓값을 구함
    def devide(l,r):
        if l>r:
            return 0
        m = query(l,r)
        area = (r-l+1)*h[m]
        left = devide(l,m-1)
        right = devide(m+1,r)
        return max(area,left,right)

    return devide(0,n-1)



while True:
    t = input()
    if t=='0':
        break

    h = list(map(int, t.split()))
    print(solve(h[1:]))

 

 

 

 

단조 스택(monotonic stack)을 사용한 풀이

 

단조 스택이란, 스택 내부의 요소를 항상 오름차순(단조 증가) 또는 내림차순(단조 감소)으로 관리되는 스택을 말한다.

 

단조 증가 스택을 사용해서 막대의 인덱스를 저장하는데, 인덱스에 해당하는 막대의 높이가 항상 오름차순으로 정렬되게 해 주었다.

 

스택이 비어있거나, 스택의 최상단의 막대의 높이보다 넣으려는 인덱스의 막대의 높이가 크거나 같으면 스택에 넣어준다.

스택에 최상단에 있는 막대의 높이보다 넣으려는 막대의 높이가 낮다면, 스택에서 하나를 꺼내어 그 막대의 높이를 height, 꺼낸 값의 인덱스와 스택 최상단의 인덱스의 차이를 width로 해는 직사각형의 넓이 최댓값을 구해주면 된다.

 

 

 

스택이 비어있으니 0번 인덱스를 넣는다.

 

 

 

넣으려는 막대(1번)의 높이가 스택의 최상단(0번) 보다 작다. 따라서 스택에서 하나를 꺼낸다.

height는 스택에서 꺼낸 막대의 높이(0번 막대의 높이), width는 넣으려는 막대의 인덱스-스택 최상단 막대의 인덱스+1인데 스택이 비어있으므로 넣으려는 막대의 인덱스가 된다.

따라서 height는 2, width는 1이 된다.

 

 

 

 

 

 

1번, 2번, 3번 막대는 각각 스택의 최상단 막대보다 크므로 차례대로 넣어준다.

 

 

 

 

 

4번 막대는 스택의 최상단보다 작다. 따라서 스택에서 꺼내면서, 넓이를 업데이트해준다.

스택에서 꺼낸 막대는 3번 막대이고 height는 5이다. 너비는 넣으려는 막대의 인덱스(4)-스택 최상단 막대 인덱스(2)+1 = 1이다.

 

 

 

 

 

 

스택에서 꺼낸 막대는 2번 막대이고 height는 4이다. 너비는 넣으려는 막대의 인덱스(4)-스택 최상단 막대 인덱스(1)+1 = 2이다.

 

 

 

 

스택에서 꺼낸 막대는 1번 막대이고 height는 1이다. 너비는 넣으려는 막대의 인덱스(4) = 4이다.

이 과정을 반복해 주게 되면 넓이의 최댓값을 구할 수 있다.

 

 

def solve(h):
    # 나중에 스택에 남아있는 값을 전부 비우기 위해 
    # 높이의 최솟값을 마지막 위치에 넣어줌
    h.append(0)
    stack= []
    answer = 0
    for i in range(len(h)):
        # 현재값이 스택의 최상단 값보다 작다면 꺼냄(스택 요소의 오름차순 유지)
        while stack and h[stack[-1]]>h[i]:
            # 스택에서 꺼내고 넓이를 계산하여 업데이트해줌
            index = stack.pop()
            width = i if not stack else i-stack[-1]-1
            area = h[index] * width
            answer = max(answer,area)
        stack.append(i)
    return answer

while True:
    t = input()
    if t=='0':
        break

    h = list(map(int, t.split()))
    print(solve(h[1:]))

 

 

 

단조 스택을 사용해서 풀었을때 세그먼트 트리로 풀었을 때보다 8배 정도 빠르다.