구름LEVEL - (43102) 울타리 자르기

2021, 04월 15일 2 분 소요

구름LEVEL - 울타리 자르기

문제 설명

입력

첫 줄에는 판자의 수(20000 이하의 자연수)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기

입/출력 예시

예시 1

입력

7
7 1 5 9 6 7 3

출력

예시 2

입력

4
1 8 2 2

출력

풀이

먼저 DFS를 이용하여 첫번째 울타리 부터 자를 수 있는 경우의 수를 모두 뽑아내어 최댓값을 리턴하도록 구현했다. 구름 LEVEL의 테스트 케이스는 통과했지만 좀더 긴 울타리 배열을 가지고 테스트를 했을 때는 시간이 오래걸려서 제출시에 시간초과가 뜰것이라고 예상했다.

그런데 혹시나 하는 마음에 DFS 알고리즘으로 제출을 해보았는데 통과되어서 당황했다.. 입력 조건에 판자의 개수가 최대 20000개로 명시되었지만 구름 LEVEL의 테스트 케이스 개수가 부족해서 통과된 것 같았다.

하지만 DFS 알고리즘의 시간복잡도 때문에 정답이 아니라고 생각했고 더 좋은 알고리즘을 생각해보았다.

먼저 기존의 DFS 알고리즘은 최악의 경우 O(n^2)의 시간복잡도를 가진다.

따라서 Divide and Conquer(분할 정복법)을 이용하여 문제를 해결해보았다.

울타리 배열을 반으로 나누어 재귀호출하여 연산을 수행하면 된다고 생각했다. 하지만 문제에서 요구하는 최댓값이 울타리의 중간(mid)를 포함할 수도 있기 때문에 해당 경우의 수도 함께 포함하여 비교연산을 해야했다. 이는 배열의 쵀대 부분 합을 구하는 알고리즘과 유사한 성격을 가진다.

분할 정복을 이용하여 O(n log n)의 시간복잡도 만큼 줄일 수 있었다.

코드(Python)

DFS 알고리즘으로 구현한 코드 (시간 초과)

def dfs(now, arr, width, result):
    if now>arr[0]:
        result.append(now*width)
        now = arr[0]
    if len(arr)==1:
        if now <= arr[0]:
            result.append(now*(width+1))
        else:
            result.append(now*(width))
        return    
    for i in range(1, now+1):
        dfs(i, arr[1:], width+1, result)
    if now<arr[0]:
        for i in range(now+1, arr[0]+1):
            dfs(i, arr[1:], 1, result)

n = int(input())
arr = list(map(int, input().split()))

result = []
dfs(arr[0], arr[1:], 1, result)
print(max(result))

Divide and Conquer 알고리즘으로 구현한 코드

def binary_search(arr, a, b):
    if a == b:
        return arr[a]
    mid = int((a+b)/2)
    # 울타리의 부분 배열(a ~ mid, mid+1 ~ b) 중 최대 넓이 계산
    answer = max(binary_search(arr, a, mid), binary_search(arr, mid+1, b))
        
    # mid에서 width : 2, height min(arr[l], arr[r])으로 이루어진 직사각형
    l = mid
    r = mid+1
    h = min(arr[l], arr[r])
    # 기존의 최대 넓이와 비교
    answer = max(answer, 2 * h)
    
    # mid를 포함하는 직사각형의 width에서 l, r을 넓혀가며 최대 넓이와 비교
    while l > a or r < b:
        if r < b and (l == a or arr[r+1] > arr[l-1]):
            r += 1
            h = min(h, arr[r])
        else:
            l -= 1
            h = min(h, arr[l])
        answer = max(answer, (r-l+1) * h)
    return answer

n = int(input())
arr = list(map(int, input().split()))

print(binary_search(arr, 0, n-1))

최준규