[코딩테스트][백준] 🔥 백준 1725번 "히스토그램" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🛠️ 미해결

• 풀이시간 : 2시간 이상
• 세그먼트 트리 : 세그먼트 트리의 개념을 모르고 있던 터라 정리를 하였다. 구간에서의 특정 값을 계산하고 이를 불러오거나 업데이트하는데 $O(logn)$이 걸리는 트리 형태의 자료구조이다. 구간 합 뿐만 아니라 최소, 최대 값을 다룰 수도 있다는 점을 모르고 있었다.

🕒 Python 풀이시간: x

import sys
sys.setrecursionlimit(10**5)

N=int(input())

arr=[]
for _ in range(N):
    arr.append(int(input()))

tree=[0]*(4*N)

def build_segment_tree(tree,arr,node,start,end):
    if start==end:
        tree[node]=(arr[start],start)
    else:
        mid=(start+end)//2
        build_segment_tree(tree,arr,node*2,start,mid)
        build_segment_tree(tree,arr,node*2+1,mid+1,end)
        tree[node]=min(tree[node*2],tree[node*2+1])

def range_query(tree,node,start,end,L,R):
    if R<start or L>end:
        return (1e9,1e9)
    elif L<=start and end<=R:
        return tree[node]
    else:
        mid=(start+end)//2
        left_min=range_query(tree,node*2,start,mid,L,R)
        right_min=range_query(tree,node*2+1,mid+1,end,L,R)
        return min(left_min,right_min)

def getSize(tree,left,right):
    minH,minIdx=range_query(tree,1,0,N-1,left,right)

    nSize=(right-left+1)*minH

    if left<minIdx:
        nSize=max(getSize(tree,left,minIdx-1),nSize)
    if minIdx<right:
        nSize=max(getSize(tree,minIdx+1,right),nSize)
    return nSize

build_segment_tree(tree,arr,1,0,N-1)
print(getSize(tree,0,N-1))

히스토그램 최대 직사각형 넓이 구하기! 📊📏

히스토그램이 각 높이를 통해 주어졌을 때, 구해질 수 있는 직사각형의 최대 넓이를 구하는 문제이다. 이 때, 높이의 범위가 10억이내이고 밑변의 최대 길이가 100,000이므로 NlogN 정도의 시간복잡도가 걸릴 것이라 예상하였다.

현재의 구간에서의 최대 넓이를 구하는데, 이때 필요한 것은 구간에서의 최소 합이므로 이를 세그먼트 트리를 통하여 logN으로 빠르게 가져올 수 있다. 이렇게 구한 높이를 통하여 현재에서의 넓이를 구해주고 이 최소 높이를 가지는 부분을 기준으로 해서 왼쪽과 오른쪽에서의 최대 넓이도 구한다. 이렇게 분할 정복을 해 들어가면 되는 것이다.

이렇게 Python으로 백준의 "히스토그램" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊