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

백준 - 6549 히스토그램에서 가장 큰 직사각형

문제

 

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

 

 

 

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

문제해결방법 - stack, 분할정복(서칭 참고)

 

1. stack을 이용하는 경우 직사각형 높이 리스트 양 옆에 [0]을 더해줘서 누락되는 계산이 없도록 하는 점이 흥미롭다.

(활용가능성을 염두) stack에는 인덱스를 저장하고 빼게 되며 작아질 때마다 스택에 두었던 직사각형 높이 리스트를 길이와 더불어 곱하여 최댓값을 계속 갱신하는 구조로 진행하게 된다. 

 

1) 높이와 곱해줄 길이 lth를 (i - stack[ - 1] - 1) 로 하지 않는 경우 스택에 이미 빠져있는 더 큰 요소의 길이가 반영되지 않을 수 있다. 현재 도는 d[ i ]보다 작은, 빠지지 않는 stack[ - 1] 을 기준삼아 길이를 구할 수 있다.

 

2. 분할정복 재귀함수의 경우 mid, mid+1로 나누어 양 옆으로 인덱스를 진행하며 직사각형의 높이 최소값에 길이를 곱해 최댓값을 갱신하는 방식으로 이루어진다. 갑자기 커지는 경우도 있으므로 재귀함수로 같은 방법으로 진행하며 누락되는 계산이 없도록 한다.

 

-코드

stack

import sys
input = sys.stdin.readline

def Monotonic_Stack(an):
    stack = [0]
    ans = 0
    for i in range(1, len(an)):
        while stack and an[stack[-1]] > an[i]:
            node = stack.pop()
            lth = i - stack[-1] - 1
            ans = max(ans, an[node] * lth)
        stack.append(i)
    return ans

while True:
    an = list(map(int, input().split()))
    if an[0] == 0:
        break
    an = [0] + an[1:] + [0]
    print(Monotonic_Stack(an))

 

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

def MntnS(an):
    stack = []
    ans = 0
    for i in range(len(an)):
        start = i # start에 일단 0이 들어간다.
        while stack and stack[-1][1] >= an[i]:
            idx, hght = stack.pop() # idx에는 start가 저장되어있음. start는 한 싸이클 이후 
            lth = i - idx           # 에도 막대길이 계산이 전의 요소까지 인식되도록 한다.
            ans = max(ans, hght * lth) # stack에 첫항은 0이 들어간 것이 마지막 낮은요소 * 길이 계산
            start = idx                # 이 가능하도록 한다.
        stack.append((start, an[i]))
    while stack:                    # 마지막 stack에 남은 요소를 반영해야한다. 
        idx, hght = stack.pop()     # 수열 마지막에 + [0] 면 생략 가능
        lth = len(an) - idx
        ans = max(ans, hght * lth)
    return ans

while True:
    an = list(map(int, input().split()))
    if an[0] == 0:
        break
    an = an[1:]
    print(MntnS(an))

분할정복

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

def sol(start, end):
    if start == end:
        return an[start]
    mid = (start + end) // 2
    l, r = mid, mid+1
    lth = 2
    min_hght = min(an[l], an[r])
    width = min_hght * lth
    while True:
        if l == start and end == r:
            break
        if l == start:
            r += 1
            min_hght = min(min_hght, an[r])
        elif r == end:
            l -= 1
            min_hght = min(min_hght, an[l]) # 양방향 중 한 쪽이 마무리되었을 때를 먼저  
        else:
            if an[r+1] > an[l-1]:           # 양방향 둘다 마무리가 안되었을 때
                r += 1
                min_hght = min(min_hght, an[r])
            else:
                l -= 1
                min_hght = min(min_hght, an[l])
        lth += 1
        width = max(width, min_hght * lth)
    sol_left = sol(start, mid)
    sol_right = sol(mid+1, end)
    return max(width, sol_left, sol_right)

while True:
    an = list(map(int, input().split()))
    if an[0] == 0:
        break
    an = an[1:]
    print(sol(0, len(an)-1))