[Baekjoon]백준 6549 히스토그램에서 가장 큰 직사각형(플래티넘 5) - Python

문제설명

문제를 살펴보면 히스토그램이 주어지고, 이 히스토그램에서 그릴 수 있는 가장 큰 직사각형을 찾아

그 넓이를 출력하면 되는 문제이다 높이가 가장 높은 index부터 확인을 하게 되면 우리의 입장에서는 간단하지만

이를 코딩을 하기에는 왼쪽, 오른쪽으로 나누어 별도로 처리해야한다 또한 최대 넓이를 계산하기 위해

for문을 두개 사용하게 되면 O(N^2)의 시간이 걸린다

 

그래서 이분 탐색의 원리처럼 중간 index를 기준 하나 첫 index부처 중간 index까지의 경우, 중간 index부터 끝 index까지의 경우 총 3개로 나누어 계산하는 로직을 생각하였다 이 방식을 사용하면 해당 함수를 재귀적으로 호출하면서

index의 범위를 인자로 전달하기 때문에 분할 정복의 방식으로 해결할 수 있다 이후 while문에서 각 영역을 이동하면서 최대 넓이를 갱신하기 때문에 이 코드의 시간복잡도는 O(NlogN)이 된다

import sys

def sol(left, right):
    if left == right:
        return Rec[left]
    mid = (left + right) // 2
    width = 2
    min_height = min(Rec[mid], Rec[mid+1])
    max_area = min_height * width
    
    move_left = mid
    move_right = mid + 1
    # 왼쪽으로 이동하는 index와 오른쪽으로 이동하는 index가 범위 내에 존재할 때 반복
    while left < move_left or move_right < right:
        # 오른쪽으로 더이상 index이동이 불가능하거나, 왼쪽 index의 높이가 더 높은 경우
        if move_right == right or Rec[move_left-1] > Rec[move_right+1]:
            move_left -= 1
            width += 1
            min_height = min(min_height, Rec[move_left])
            max_area = max(max_area, min_height*width)
        # 왼쪽으로 더이상 index이동이 불가능하거나, 오른쪽 index의 높이가 더 높은 경우
        else:
            move_right += 1
            width += 1
            min_height = min(min_height, Rec[move_right])
            max_area = max(max_area, min_height*width)
            
    max_area = max(max_area, sol(left, mid), sol(mid+1, right))
    return max_area
            
        
while True:
    Rec_ = list(map(int, sys.stdin.readline().split()))
    if Rec_[0] == 0:
        break
    Rec = Rec_[1:]
    print(sol(0, Rec_[0]-1))

중간지점을 기준으로 분할하며 함수를 호출하고, 해당 함수에서 최대 넓이를 구하여 이를 return하고 있다

그러나 이를 제출하였을때 시간초과가 발생하는 것을 확인하였다

그래서 같은 방식으로 해결한 다른 분들의 코드를 보아도 이 코드와 거의 동일하였지만, 혹시나 싶어

sys.setrecursionlimit(10**6) 코드를 추가하여도 똑같이 시간초과가 발생하는 것을 확인할 수 있었다

결국 GPT의 도움을 받아 다른 방식으로 문제를 해결하였다

GPT는 이 코드에서 스택을 활용하여 시간복잡도를 O(N)으로 개선하였다

히스토그램을 순회하면서 최대넓이를 계산하는 방식으로 해결하였고, 이전보다 작은 높이를 만나면

스택에서 꺼내어 넓이를 계산하는 방식으로 작성하였 

 

for문을 통해 히스토그램을 한 번씩 순회하면서 while문을 통해 스택의 상태에 따라 max_area를 갱신한다

자세하게 설명하자면 스택을 돌면서 스택의 최상단 높이(가장 최근에 추가된 높이)보다 작은 경우

스택에서 pop을 하여 max_area를 갱신하게 되고, 너비의 경우 스택이 비어있다면 width = 1이 될 것이다

스택이 남아 있다면 가장 가까운 왼쪽 히스토그램 다음부터 i-1까지 확장이 가능하므로 width = i - stack[-1] - 1이 된다

import sys

def sol(Rec):
    Rec.append(0)  # 마지막 원소로 작은 값 0을 추가하여 스택이 비워지도록 도와줌
    stack = []
    max_area = 0

    for i in range(len(Rec)):
        while stack and Rec[stack[-1]] > Rec[i]: # 스택의 최상단 높이보다 작은 경우 max_area 갱신
            height = Rec[stack.pop()]
            if not stack:
                width = i  # 스택이 비어 있다면, 현재 막대는 0부터 i까지 확장 가능
            else:
                width = i - stack[-1] - 1  # 왼쪽의 낮은 막대 바로 오른쪽부터 현재 i-1까지 확장 가능
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

while True:
    Rec_ = list(map(int, sys.stdin.readline().split()))
    if Rec_[0] == 0:
        break
    Rec = Rec_[1:]
    print(sol(Rec))

첫 플래티넘 문제였는데, 그만큼 생각하는 시간도 증가하고 해결과정도 순탄하지 않았던 것 같다