[Python] 백준 6549번: 히스토그램에서 가장 큰 직사각형

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

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

 

import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)


def get_tree_length(N):
    if N & (N-1) == 0:
        return 2*N
    else:
        return pow(2, math.ceil(math.log(N, 2)) + 1)


def initialize_segtree(index, start, end):
    if start == end:
        tree[index] = start
        return

    mid = (start + end)//2
    initialize_segtree(index*2, start, mid)
    initialize_segtree(index*2+1, mid+1, end)

    # Returns lower one
    if nums[tree[index*2]] < nums[tree[index*2+1]]:
        tree[index] = tree[index*2]
    else:
        tree[index] = tree[index*2+1]


def query_segtree(index, start, end, left, right):
    # For an exception
    if right < start or end < left:
        return -1

    if left <= start and end <= right:
        return tree[index]

    mid = (start+end)//2
    l = query_segtree(index*2, start, mid, left, right)
    r = query_segtree(index*2+1, mid+1, end, left, right)

    # Handle out of range exception
    if l == -1 or r == -1:
        return max(l, r)
    else:
        # Returns lower one
        if nums[l] < nums[r]:
            return l
        else:
            return r


def get_square_area(start, end):
    if start == end:
        return nums[start]

    # Get lowest height
    index = query_segtree(1, 1, nums[0], start, end)
    areas = [(end-start+1)*nums[index]]

    # Is in range?
    if index-1 >= start:
        areas.append(get_square_area(start, index-1))
    if index+1 <= end:
        areas.append(get_square_area(index+1, end))

    return max(areas)


if __name__ == '__main__':
    # Do while
    nums = list(map(int, input().split()))
    while nums[0] != 0:
        # Initialize segment tree
        tree = [0]*get_tree_length(nums[0])
        initialize_segtree(1, 1, nums[0])

        # Solution
        print(get_square_area(1, nums[0]))

        # Get next input
        nums = list(map(int, input().split()))

 

get_square_area() 함수에서, 가장 낮은 곳의 인덱스를 가져와서(세그먼트 트리를 이용), 그것을 기준으로 앞뒤로 자른다.

위 사진에서 가장 큰 직사각형의 후보는 총 3개가 있다. 각각 가장 낮은 높이에서의 직사각형, 파란색 왼쪽 직사각형, 파란색 오른쪽 직사각형이다. 여기서 파란색 구간에 get_square_area()로 재귀 함수를 호출해주는 식이며, 마지막으로 이 3개의 넓이 중 가장 큰 것을 리턴해준다.

 

앞서 언급하였듯이 Segment Tree를 통해 가장 낮은 곳의 인덱스를 가져와준다. 이를 위해 세그먼트 트리를 응용하여 설계해야하며, 크게 어려운 점은 없으니 부족한 설명은 주석이 채워주리라 믿는다.

 

 

이 문제에서 가장 중요한 건, 가장 작은 곳을 기준으로 나누어 푼다는 것이다. 나는 세그먼트 트리에 어떤 정보를 담아내서 query로 바로 가장 큰 직사각형의 넓이를 구할 수 있는 줄 알고 한참을 헤맸다.

 

---

Stack을 이용한 최적의 풀이(monotonic stack)

 

import sys
input = sys.stdin.readline


def solution(nums):
    res = 0

    length = nums[0]
    stack = [0]  # 인덱스를 저장
    nums[0] = 0  # 반복문 초기에 nums[stack[0]], 즉 nums[0]과 값을 비교하는데, 이에 대한 처리임
    nums.append(0)  # 마지막 인덱스에서의 연산을 위함

    for i in range(1, length+2):
        while nums[stack[-1]] > nums[i]:
            index = stack.pop()
            res = max(res, (i - (stack[-1] + 1))*nums[index])

        stack.append(i)

    return res


if __name__ == '__main__':
    nums = list(map(int, input().split()))
    while nums[0] != 0:
        print(solution(nums))
        nums = list(map(int, input().split()))