BOJ 6549 히스토그램에서 가장 큰 직사각형 python

세그먼트 트리 만들기. [높이가 최소인 막대의 index, 막대의 높이] * (n*4)
높이가 최소인 막대의 index를 트리에서 찾기
(최소 높이)*(구간의 길이)를 저장.
2에서 구한 index를 기준으로 구간을 둘로 나누고 2부터 반복.

세그먼트 트리 알고리즘을 처음 써봤다. 트리 조회 부분 알고리즘이 신박했다. 먼저 자식 트리들이 범위를 벗어나는지를 체크한다. 범위를 벗어나는 경우에는 반대쪽 트리를 조회하고, 둘 다 범위 안일 경우에는 어차피 최소값을 구하면 되기 때문에 값이 더 작은 쪽만 조회한다. 이 문제는 큐로도 풀이가 가능하다.

풀이 코드

import sys
sys.setrecursionlimit(10**6)
def setTree(node, left, right):
    if left == right:
        tree[node] = [left, g[left]]
        return [left, g[left]]
    mid = left + (right-left)//2
    leftVal = setTree(node*2, left, mid)
    rightVal = setTree(node*2+1, mid+1, right)
    if leftVal[1] < rightVal[1]: tree[node] = [leftVal[0], leftVal[1]]
    else: tree[node] = [rightVal[0], rightVal[1]]
    return [tree[node][0], tree[node][1]]
 
def findIdx(node, start, end, left, right):
    if end < left or start > right: return -1
    if left<=start and end<=right: return tree[node]
    mid = start + (end-start)//2
    startVal = findIdx(node*2, start, mid, left, right)
    endVal = findIdx(node*2+1, mid+1, end, left, right)
    if startVal == -1: return endVal
    if endVal == -1: return startVal
    if startVal[1] > endVal[1]: return endVal
    else: return startVal
 
def find(left, right):
    idx, h = findIdx(1, 0, n-1, left, right)
    result = (right-left+1)*h
    if left <= idx-1: result = max(result, find(left, idx-1))
    if idx+1 <= right: result = max(result, find(idx+1, right))
    return result
 
while True:
    n, *g = map(int, sys.stdin.readline().split())
    if n == 0: break
    tree = [[0,0] for _ in range(n*4)]
    setTree(1, 0, n-1)
    print(find(0,n-1))