[AlgoSpot][Python] 울타리 잘라내기

📒 문제 설명

🔖 https://algospot.com/judge/problem/read/FENCE

📖 문제
너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

✍ 입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

💻 출력
각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

---

✏️ 풀이 과정

📝 1차 시도

• 가장 먼저 생각한 방법은 가능한 모든 왼쪽 경계값과 오른쪽 경계값의 조합을 순회하여 그중에서 최댓값을 구하는 것인데, 이 알고리즘의 시간 복잡도는 O(n^2). 문제의 최대 입력이 20000이므로 이 방법은 적절하지 않을 것이다.

• 그 다음으로 고려한 방법은 스택을 이용하는 것이다. 스택의 각 원소는 (인덱스, 높이)를 나타내며, max_area 배열은 해당 인덱스의 판자의 높이를 유지한 채로 잘라낼 수 있는 울타리 넓이의 최댓값을 저장할 것이다.

• 높이 배열을 순회하며, 현재 높이가 스택의 맨 위에 위치한 원소의 높이보다 클 때까지 pop한다. 현재 높이가 스택의 맨 위에 위치한 원소보다 크면 현재 높이에 대한 왼쪽 경계값(left_boundary)을 설정하고, 현재 높이를 스택에 추가한다.

• 특정 울타리의 오른쪽 경계는 스택에서 해당 울타리가 pop하는 시점에 결정된다. 스택에서 pop한 높이보다 현재 높이가 낮은 경우에 직사각형의 오른쪽 경계가 결정되기 때문이다.

• 스택에 저장된 모든 원소에 대하여 pop이 이루어져야 하므로, fence의 마지막 원소에 0을 추가해주었다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def solve(size, fence):
	# 처리를 용이하게 하기 위하여 다음과 같이 스택 초기화
    stack = [(-1, 0)]
    left_boundary = [0] * size
    max_area = [0] * size

    for i, h in enumerate(fence):
    	# 현재 높이가 스택의 맨 위 높이보다 클 때까지 pop
        while stack[-1][1] > h:
            j, l = stack.pop()
            max_area[j] = (i - left_boundary[j]) * l

        left_boundary[i] = stack[-1][0] + 1
        stack.append((i, h))
        
    return max(max_area)

for _ in range(int(input())):
    size = int(input()) + 1
    # `fence`의 마지막 원소에 0을 추가
    fence = list(map(int, input().split())) + [0]
    print(solve(size, fence))

---

📝 2차 시도

• 교재에서는 전체 울타리의 가운데를 기준으로 왼쪽 부분 문제와 오른쪽 부분 문제, 양쪽 부분 문제에 걸친 경우로 나누어 풀이했다. (분할 정복)

• 양쪽 부분 문제에 걸친 경우를 구하기 위해 그림과 같이, [mid, mid + 1]만 포함하는 너비가 2인 사각형에서 시작하여 왼쪽 경계값과 오른쪽 경계값을 이동하면서 최댓값을 구한다.

• 울타리를 수평으로 확장하는 순서의 기준은 단순히 더 높은 방향으로 확장하는 것이다. 이러한 방식으로 양쪽 끝까지 수평으로 울타리를 확장해가며 최댓값을 갱신한다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def solve(fence, left, right):
    # 기저 사례: 판자가 하나만 있는 경우
    if (left == right): return fence[left]

    mid = (left + right) // 2
    # 왼쪽 부분 문제와 오른쪽 부분 문제로 분할
    result = max(solve(fence, left, mid), solve(fence, mid + 1, right))
    
    # 양쪽 부분 문제에 걸친 경우
    left_bound, right_bound = mid, mid + 1
    height = min(fence[left_bound], fence[right_bound])
    result = max(result, height * 2)
	
    # 울타리의 양쪽 끝에 도달할 때까지 확장
    while left < left_bound or right_bound < right:
    	# 높이가 더 높은 판자가 위치한 쪽으로 먼저 확장
        if right_bound < right and (left_bound == left or fence[left_bound - 1] < fence[right_bound + 1]):
            right_bound += 1
            height = min(height, fence[right_bound])
        else:
            left_bound -= 1
            height = min(height, fence[left_bound])
        result = max(result, height * (right_bound - left_bound + 1))

    return result

for _ in range(int(input())):
    size = int(input())
    fence = list(map(int, input().split()))
    print(solve(fence, 0, size - 1))