Baekjoon 6549. 히스토그램에서 가장 큰 정사각형 / Python

6549. 히스토그램에서 가장 큰 정사각

난이도 : 플래티넘 5
소요 시간 : 35분
날짜 : 2025.01.05
언어 : 파이썬
알고리즘 유형 : 분할정복, 세그머트트리, 스택

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 히스토그램의 내부의 직사각형들 중 가장 넓이가 큰 직사각형을 구하기

2. 해결 방식

1. 스택 활용

   • 히스토그램을 순회하면서 현재 높이보다 낮은 높이를 만날 때마다 직사각형 넓이를 계산한다.
   • 0을 만난다면 스택을 초기화한다.
   • 시간복잡도 : O(n)

2. 세그먼트트리

   • 각 구간의 최소 높이를 세그먼트 트리로 저장한다.
   • 구간의 최소높이 * 구간의 크기 = 넓이
   • 전체 시간복잡도: O(nlongn)

3. 분할정복(사용하지 않았지만, 가능한 방법)
   • (히스토그램에서 가장 낮은 높이를 기준으로 좌우로 분할)을 반복하는 방식
   • 시간 복잡도 : O(nlongn)

     3. 정답 코드

import sys; input = sys.stdin.readline

while 1:
    n, *heights = map(int, input().split())
    if not n:break

    res = 0
    stack = []
    for i in range(n + 1):
        now = heights[i] if i != n else 0
        idx = None        
        while stack and stack[-1][0] >= now:
            h, idx = stack.pop()
            res = max(res, (i - idx) * h)

        stack.append((now, idx if idx is not None else i))

    print(res)

참고
:세그먼트트리를 활용한 코드
:시간은 O(nlongn)이라서 통과할 것 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def make_tree(h, tree, node, s, e):
    if s == e:
        tree[node] = s
        return tree[node]
    mid = (s + e) // 2
    l_idx = make_tree(h, tree, node * 2, s, mid)
    r_idx = make_tree(h, tree, node * 2 + 1, mid + 1, e)
    tree[node] = l_idx if h[l_idx] <= h[r_idx] else r_idx
    return tree[node]

def find_min_height(tree, h, node, s, e, l, r):
    if l > e or r < s:
        return -1
    if l <= s and e <= r:
        return tree[node]
    mid = (s + e) // 2
    l_idx = find_min_height(tree, h, node * 2, s, mid, l, r)
    r_idx = find_min_height(tree, h, node * 2 + 1, mid + 1, e, l, r)

    if l_idx == -1:return r_idx
    if r_idx == -1:return l_idx

    return l_idx if h[l_idx] <= h[r_idx] else r_idx


def sol(h, tree, s, e):
    if s > e:
        return 0
    min_idx = find_min_height(tree, h, 1, 0, len(h) - 1, s, e)
    area_with_min_height = h[min_idx] * (e - s + 1)
    left_area = sol(h, tree, s, min_idx - 1)
    right_area = sol(h, tree, min_idx + 1, e)
    return max(area_with_min_height, left_area, right_area)

while True:
    n, *h = map(int, input().split())
    if n == 0:
        break
    tree = [0] * (4 * n)
    make_tree(h, tree, 1, 0, n - 1)
    print(sol(h, tree, 0, n - 1))

참고
:분할정복을 활용한 코드
:높이가 모두 같은 경우 최악 시간복잡도는 O(n^2) - n이 100,000이라 안 될듯.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def largest_rectangle(heights, start, end):
    # 빈 구간
    if start > end:
        return 0

    # 구간 내 최소높이 찾기
    min_idx = start
    for i in range(start, end + 1):
        if heights[i] < heights[min_idx]:
            min_idx = i

    # 최소 높이를 기준으로 넓이를 계산
    area_with_min_height = heights[min_idx] * (end - start + 1)

    # 좌우 구간에 대해 재귀
    left_area = largest_rectangle(heights, start, min_idx - 1)
    right_area = largest_rectangle(heights, min_idx + 1, end)

    return max(area_with_min_height, left_area, right_area)

while 1:
    # 입력을 처리
    n, *heights = map(int, input().split())
    if not n:
        break

    print(largest_rectangle(heights, 0, n - 1))