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

문제

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

1725번과 6549번은 사실 같은 문제이다. 분할정복 문제라서 도전해봤는데 생각보다 어렵다. 알고보니 스택으로 푸는 법과 분할정복으로 푸는 법, 세그먼트트리로 푸는 법이 따로 있다고 한다. 스택으로 푸는 것이 시간복잡도가 O(n)으로 가장 빠르고 쉬운 풀이라고 하는데, 그래도 어렵다. 나는 솔루션을 보고 이해했다. 스택으로 될 것 같아서 도전했는데 안되더라. 분할정복 솔루션도 봤는데 그건 더 어렵다..

나의 풀이

스택으로 풀 수 있을 것 같아서 도전했다. 나중에 보니 스택으로 푸는 법과 로직은 거의 같았는데 가장 긴 아래 밑변 구하는 것을 못해서 틀렸다. 아쉽군. 우선 나는 두 가지 방식을 사용했다. 첫 번째는 아래 솔루션 1과 거의 유사하다. 두 번째는 스택과 재귀를 사용했다. 히스토그램의 높이가 증가할 때 스택에 담고, 감소하면 재귀를 사용해 스택에 담겨있는 직사각형의 최대 넓이를 구하는 방식을 사용했다. 그러나 틀렸다. 솔루션을 보고나니 왜 틀렸는지 알았다.

솔루션 1: 스택

히스토그램 스택 풀이

솔루션은 간단하기 그지없다. 왼쪽에서부터 시작하여 히스토그램이 증가하면 stack에 담고, stack[-1] 보다 작은 값을 만나면 그보다 작거나 같은 값이 보이기 전까지 stack.pop()을 한다. pop을 하면서 직사각형의 넓이를 구하고 최대값을 갱신하면 된다.

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]

answer = a[0]
stack = [0]
for i in range(1, n):
    while stack and a[stack[-1]] > a[i]:
        mIdx = stack.pop()
        if stack:
            width = i - stack[-1] - 1
        else:
            width = i
        answer = max(answer, width*a[mIdx])
    stack.append(i)

while stack:
    mIdx = stack.pop()
    if stack:
        width = n - stack[-1] - 1
    else:
        width = n
    answer = max(answer, width*a[mIdx])

print(answer)

솔루션 2: 분할정복

히스토그램 분할정복 풀이

분할정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다.

1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우
2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우
3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우

1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다.

솔루션 3: 세그먼트 트리