[BOJ] 6549 - 히스토그램에서 가장 큰 직사각형 (Python)

 

 

아이디어 #1

 

분할 정복으로 해당 범위에서 만들 수 있는 가장 큰 직사각형의 넓이를 구해 나간다.

 

 

풀이 #1

 

각 테스트 케이스의 첫 번째 수는 N, 나머지 직사각형의 높이들은 H에 입력 받아 N이 0이 아닌 동안 while문을 반복한다.

 

함수 find에서는 인자로 받은 l부터 r까지의 범위에서 가장 큰 직사각형 넓이를 찾는다.

l과 r이 같으면 그 직사각형 높이를 반환하고, 그렇지 않으면 포인터 s와 e에 각각 현재 범위 중간인 m과 m+1을 할당한다.

 

반환값 res에는 가운데 두 직사각형을 합쳐 만들 수 있는 직사각형의 넓이 h*2와

재귀 호출로 가운데를 기준으로 왼쪽과 오른쪽에서 가장 큰 직사각형 넓이 중 최댓값을 할당한다.

 

while문에서는 s부터 e까지의 범위에서 만들 수 있는 직사각형의 넓이를 구해 res에 그 최댓값을 저장해 나간다.

s, e는 가운데에서부터 양끝에 닿을 때까지 이동하며, 다음 직사각형 높이가 더 큰 포인터를 먼저 움직인다.

 

import sys

input = sys.stdin.readline

def find(l, r):
    if l == r:
        return H[l]
    m = (l+r)//2
    s, e = m, m+1
    h = min(H[s], H[e])
    res = max(2*h, find(l, m), find(m+1, r))
    while s > l or e < r:
        if e == r or s > l and H[s-1] >= H[e+1]:
            s -= 1
            if H[s] < h:
                h = H[s]
        else:
            e += 1
            if H[e] < h:
                h = H[e]
        res = max(res, h*(e-s+1))
    return res

while 1:
    N, *H = map(int, input().split())
    if N == 0:
        break
    print(find(0, N-1))

 

 

 

아이디어 #2

 

스택을 이용하여 각 위치에서 해당 직사각형의 높이로 만들 수 있는 가장 큰 직사각형 넓이를 구해 나간다.

 

 

풀이 #2

 

각 테스트 케이스의 첫 번째 수는 N, 나머지 직사각형의 높이들은 H에 입력 받아 N이 0이 아닌 동안 while문을 반복한다.

 

함수 solution에서는 N과 끝에 0을 추가한 H를 인자로 넘겨 가장 큰 직사각형의 넓이를 구해 출력한다.

 

직사각형의 넓이를 구하기 위해서는 직사각형의 왼쪽 끝 위치, 오른쪽 끝 위치, 높이가 필요하다.

스택 stack에는 직사각형의 위치들을 저장하며, 이 위치로 H에서 해당 직사각형의 높이를 알 수 있고,

해당 위치에서 해당 높이로 만들 수 있는 가장 넓은 직사각형의 양끝 위치는 더 작은 높이의 직사각형 끝이다.

 

for문에서는 차례로 직사각형 높이가 증가하면 그 위치를 스택에 넣고 감소하면 스택에서 위치를 꺼내 그 넓이를 계산한다.

위치 i의 직사각형 높이가 stack[-1] 위치의 직사각형 높이보다 작다면

stack[-1] 위치의 가장 넓은 직사각형의 오른쪽 끝은 위치 i-1이 되고, 왼쪽 끝은 stack[-2]+1이 된다.

 

stack에 초기값으로 -1을 넣어두고, for문에서 처음 i가 0일 때는 while문이 실행되지 않으므로 stack에 0이 추가된다.

스택에는 직사각형의 높이가 증가하는 형태로 그 위치들이 저장되는데,

H 끝에 0을 추가하여 for문에서 i가 N일 때 스택에 남아 있는 위치의 직사각형 넓이들을 계산하도록 한다.

 

import sys

input = sys.stdin.readline

def solution(N, H):
    res = 0
    stack = [-1]
    for i in range(N+1):
        while stack and H[i] < H[stack[-1]]:
            idx = stack.pop()
            l = stack[-1]
            res = max(res, H[idx]*(i-(l+1)))
        stack.append(i)
    print(res)

while 1:
    N, *H = map(int, input().split())
    if N == 0:
        break
    solution(N, H+[0])