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

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

6549번: 히스토그램에서 가장 큰 직사각형

 

이번 문제는 히스토그램에서 가장 큰 직사각형 문제이다.

문제에서 주어진 히스토그램에서 가장 넓이가 넓은 직사각형을 찾는 문제인데, 먼저 완전 탐색으로 푸는 방법을 생각해 보자.

이 문제를 완전 탐색으로 풀기 위해서는 어떤 한 블록을 기준으로 잡았을 때, 그 블록의 높이로 만들 수 있는 직사각형의 넓이를 찾아야 한다. 예를 들어 위의 예시에서 높이가 5인 블록을 기준으로 잡았다고 생각해 보자.

위와 같이 기준 블록을 잡은 뒤에는 왼쪽과 오른쪽으로 더 이상 확장할 수 없을 때까지 범위를 넓혀가며 직사각형의 넓이를 계산해 준다. 여기서 더 이상 확장할 수 없는 경우란, 각각의 인덱스가 배열의 범위 경곗값에 다다른 경우이거나, 그렇지 않은 경우 인덱스가 가리키는 블록의 높이가 기준 블록의 높이보다 작은 경우이다.

이렇게 모든 블록에 대해서 위의 과정을 진행해 주면 가장 넓은 직사각형의 넓이를 찾을 수 있다!

하지만 이러한 경우 시간복잡도가 $O(n^2)$ 이 되어버리고, 문제에서 히스토그램의 최대 크기가 100,000 이기 때문에 시간제한 조건을 만족하지 못하게 된다. 따라서 이 문제는 완전 탐색이 아닌 다른 방법으로 풀어야 한다.

나는 이 문제를 크게 두 가지 방식으로 풀었다. 하나는 분할 정복을 활용한 풀이고, 나머지 하나는 스택을 활용한 풀이이다.

분할 정복을 활용한 풀이

먼저 분할 정복을 활용한 풀이를 알아보자. 분할을 하는 방식도 다양하지만, 이 문제에서 나는 배열의 가운데를 기준으로 분할하는 방식을 선택했다.

 

그림은 완전 탐색에서 활용한 예시를 똑같이 활용했다. 만약 배열의 크기가 2보다 큰 경우에는 가운데 인덱스를 중심으로 배열을 분할한다.

 

배열을 더 이상 나누지 못하는 경우, 즉 배열의 범위가 1이거나 2인 경우에는, 해당 범위에서 만들 수 있는 직사각형 넓이의 최댓값을 반환한다.

 

이후 분할 기준점을 중심으로 왼쪽 범위에서의 최댓값과 오른쪽 범위에서의 최댓값을 비교한 뒤, 둘 중 큰 값을 반환한다.

 

하지만 이러한 풀이에는 문제점이 있다. 넓이가 가장 큰 직사각형이 분할을 하는 기준점을 걸쳐서 존재하는 경우이다. 예를 들면 아래의 그림과 같다. 

 

위의 그림은 세 번째 블록을 기준으로 나누어진 후 각각의 범위에서 최댓값을 반환한 경우를 나타낸 그림이다. 왼쪽 범위에서의 최댓값은 12, 오른쪽 범위에서의 최댓값은 10으로 나타난다. 하지만 그림을 보면 알 수 있듯이 가장 큰 직사각형은 오른쪽 범위와 왼쪽 범위 모두에 걸쳐있는 형태로 나타나고, 이때의 최댓값은 20이다.

 

따라서 분할 정복을 이용한 풀이에서는 위의 완전 탐색에서 한 것과 같이, 중간값을 기준으로 양쪽으로 넓혀가며 최댓값을 찾는 작업이 필요하다.

 

처음에는 중간값인 8에서 시작한다. 이후 왼쪽 또는 오른쪽으로 범위를 넓혀가는데, 둘 중에 높이가 더 높은 쪽으로 확장을 진행한다.

 

따라서 그림과 같이 왼쪽으로 확장을 하게 되고, 이때의 직사각형 넓이는 12가 된다.
다음으로는 왼쪽의 높이 4보다 오른쪽의 높이 5가 더 크기 때문에 오른쪽으로 확장을 한다.

 

확장을 한 뒤의 넓이는 15가 되고, 이전의 12보다 넓이가 커졌기 때문에 최대 넓이를 갱신해 준다.
이후 높이가 7인 오른쪽으로 다시 확장을 진행한다.

 

이때 넓이는 20이 되고, 이전의 최대 넓이보다 커졌기 때문에 최대 넓이를 20으로 갱신해 준다. 마지막으로 왼쪽의 4로 확장을 진행하는데, 이 경우 최대 넓이가 변하지 않기 때문에 넓이의 갱신은 발생하지 않는다.

 

이렇게 분할 기준을 포함하는 최댓값과, 왼쪽 범위의 최댓값, 오른쪽 범위의 최댓값을 모두 구하였다. 이 셋을 비교하여 가장 큰 값이 최댓값이 될 것이다.

 

코드는 아래와 같다.

import sys

input = sys.stdin.readline

res = []

def divide_and_conquer(histogram, start, end):
    if end == start:
        return histogram[end]
    elif end - start == 1:
        if histogram[end] < histogram[start]:
            return max(2*histogram[end], histogram[start])
        else:
            return max(2*histogram[start], histogram[end])
    
    mid = (start + end) // 2
    left_area = divide_and_conquer(histogram, start, mid)
    right_area = divide_and_conquer(histogram, mid+1, end)
    left = mid-1
    right = mid+1
    mid_area = histogram[mid]
    now_height = histogram[mid]
    while start <= left and right <= end:
        if histogram[left] < histogram[right]:
            if histogram[right] < now_height:
                now_height = histogram[right]
            mid_area = max(mid_area, now_height * (right - left))
            right += 1
        else:
            if histogram[left] < now_height:
                now_height = histogram[left]
            mid_area = max(mid_area, now_height * (right - left))
            left -= 1
            
    while start <= left:
        if histogram[left] < now_height:
            now_height = histogram[left]
        mid_area = max(mid_area, now_height * (right - left))
        left -= 1
    while right <= end:
        if histogram[right] < now_height:
            now_height = histogram[right]
        mid_area = max(mid_area, now_height * (right - left))
        right += 1

    return max(left_area, right_area, mid_area)
        
            
        
res = []
while True:
    histogram = list(map(int, input().split()))
    
    if histogram[0] == 0: break
    
    n = histogram[0]
    
    res.append(divide_and_conquer(histogram, 1, n))

    
for i in res:
    print(i)

 

스택을 활용한 풀이

이번에는 스택을 활용한 풀이에 대해서 알아보자. 위의 분할 정복 방식보다는 코드도 짧은 편이고, 구현도 분할 정복에 비해 쉬운 편이다.

 

풀이 방식은 현재 스택의 맨 위에 있는 블록의 높이보다 높은 값을 가지면 스택에 추가하고, 만약 현재 블록이 스택의 마지막 블록의 높이보다 낮다면, 스택에서 현재 블록의 높이보다 높은 블록들의 넓이를 모두 계산해 주는 방식이다.

 

그림으로 나타내면 아래와 같다.

먼저 스택에 들어가는 형식은 (인덱스, 블록의 높이)이다. 높이가 8인 블록까지는 계속 높이가 증가하기 때문에 계속해서 스택에 추가된다. 이후 높이가 5인 블록이 스택에 추가되어야 하는데, 여기서 스택의 마지막 블록의 높이가 8로 현재 높이인 5보다 크기 때문에 스택에서 꺼내 넓이를 계산해주어야 한다.

 

위의 그림에서 4 - 3은 높이가 5인 블록의 인덱스 4에서 8인 블록의 인덱스 3을 뺀 것이다.

 

마찬가지로 높이가 6인 블록 또한 5보다 크기 때문에 스택에서 꺼내 넓이를 계산해 준다.

계산 이후의 현재까지의 넓이의 최댓값은 12로 갱신된다.

위의 방식으로 진행을 하다 보면 마지막 블록 3을 스택에 넣은 뒤에는 다음과 같은 결과를 얻을 수 있다.

 

이렇게 마지막 블록까지 검사를 마치고 나서, 스택이 아직 비어있지 않은 것을 볼 수 있다.

따라서 마지막에는 스택에 있는 나머지 블록들에 대해 넓이 계산을 진행해 준다. 이때 직사각형의 너비는 현재 꺼낸 원소의 인덱스에서 스택의 맨 위에 있는 원소의 인덱스를 빼주면 된다. 만약 원소를 꺼냈는데 스택의 마지막 원소가 존재하지 않는 경우, 현재 원소가 가장 마지막 원소이므로 현재 원소의 인덱스를 그대로 직사각형의 너비로 설정하면 된다.

 

위의 예제 같은 경우 계산 결과 최댓값이 32로 나온다. 코드는 아래와 같다.

 

import sys

input = sys.stdin.readline

res = []
while True:
    histogram = list(map(int, input().split()))
    if histogram[0] == 0:
        break
    stack = []
    n = histogram[0]
    max_area = 0
    for i in range(1, n+1):
        if len(stack) == 0:
            stack.append((i, histogram[i]))
        else:
            if stack[-1][1] <= histogram[i]:
                stack.append((i, histogram[i]))
            else:
                while len(stack) > 0 and stack[-1][1] > histogram[i]:
                    remove = stack.pop()
                    if len(stack) == 0:
                        width = i - 1
                    else:
                        width = i - stack[-1][0] - 1
                    max_area = max(max_area, remove[1] * width)
                stack.append((i, histogram[i]))
    while stack:
        remove = stack.pop()
        if len(stack) == 0:
            width = n 
        else:
            width = (n - stack[-1][0])
        max_area = max(max_area, remove[1] * width)
    print(max_area)