백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

접근

스택 방법에 이어 분할 정복 방법을 통해서도 문제를 풀어보았다.

2021.04.03 - [분류 전체보기] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python)

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python)

분할 정복은 주어진 길이를 절반으로 나누어 작은 단위에 대해서 연산을 반복하여 최대치를 확인하는 방법이다. 히스토그램에서 가장 큰 직사각형을 구하는 문제에서도 분할 정복 방법을 사용할 수 있는데 주의해야할 점이 한가지 있다. 절반으로 나누어 분할 연산을 하였을 때, 분할 시점을 반드시 통과하는 직사각형에 대해서도 계산하여 max 값을 구하는데 사용해주어야 한다는 점이다.

당장 주어진 예시 파일에서도 주어진 히스토그램을 3 ( 7 // 2 = 3 ) 을 기준으로 나누게 되면 max값에 해당하는 직사각형이 반으로 나눠지게 되어 기존의 분할 정복과 같이 경계선에 대해 생각하지 않으면 max 값을 놓칠 수가 있다. 따라서 분할정복을 수행하면서 다음의 값들을 비교하여 최대값을 저장해 나가면 문제를 해결할 수 있다.

1. 분할 선 기준으로 왼쪽 히스토그램에서 가장 큰 직사각형
2. 분할 선 기준으로 오른쪽 히스토그램에서 가장 큰 직사각형
3. 분할 선을 반드시 포함하는 직사각형 중 가장 큰 직사각형

분할 선을 반드시 포함하는 직사각형을 구할때는 분할선을 기준으로 양쪽으로 1칸, 즉 너비가 2인 직사각형부터 시작하여 그 사각형의 양쪽 값을 비교하여 양쪽 중 큰 값쪽으로 너비를 한칸씩 늘려가면서 너비 중 더 큰 값을 저장하는 방식으로 연산을 수행했다.

예를 들어 [3, 4, 5, 6, 7] 의 히스토그램이 있을 때 반으로 나누면 [3, 4], [5, 6, 7] 로 나누어지고, 중간값을 반드시 포함하는 첫 직사각형은 [4, 5] (최대 넓이 4 * 2 = 8) 이 된다. 이 직사각형의 양쪽 값인 3과 6을 비교하여 6이 크므로 중간값을 포함하는 두번째 직사각형은 [4, 5, 6] (최대 넓이 4 * 3 = 12) 가 되고 이어서 3과 7을 비교하여 7이 더 크므로 세번째 직사각형은 [4, 5, 6, 7] (최대 넓이 4 * 4 = 16), 그리고 오른쪽으로 끝 값에 도달했기 때문에 왼쪽으로 한칸 확장하여 마지막 직사각형은 [3, 4, 5, 6, 7] (최대 너비 3 * 5 = 15) 가 된다. 이 사각형들의 max 값은 16이므로, 중간 값을 반드시 포함하는 사각형 중 최대값은 16이고, 이 값이 해당 히스토그램의 최대 넓이 직사각형이 된다.

코드

import sys


def divdeandconquer(a):
    if len(a) == 1:
        return a[0]
    if len(a) % 2 == 1:
        a = [0] + a
    d = len(a) // 2
    x = a[:d]
    y = a[d:]
    cnt = 2
    tmpmax = min(a[d - 1], a[d])
    tmparea = tmpmax * cnt
    i = 0
    j = 0
    for _ in range(0, len(a) - 2):
        if d - 1 - i == 0:
            j += 1
        elif d + j == len(a) - 1:
            i += 1
        else:
            if a[d - 2 - i] >= a[d + 1 + j]:
                i += 1
            else:
                j += 1
        tmpmax = min(tmpmax, a[d - 1 - i], a[d + j])
        cnt += 1
        tmparea = max(tmparea, tmpmax * cnt)
    z = tmparea
    return max(divdeandconquer(x), divdeandconquer(y), z)


while 1:
    n, *histogram = list(map(int, sys.stdin.readline().split()))
    if n == 0:
        break
    maxarea = divdeandconquer(histogram)
    print(maxarea)

더 생각해 볼 것?

분할정복으로 수행 시 분할선을 포함하는 사각형의 크기를 구하는 반복 작업이 반복 작업이 커서 그런지, 스택을 이용한 방법보다 시간이 매우 오래 걸린다. 결과적으로는 기준 시간에 들어와 정답을 맞추기는 했지만, 더욱 시간을 줄일 수 있는 최적화 방법이 있는지 추가적인 공부가 필요할 것 같다. 구현이 되긴 했지만 코드도 조금 지저분한것 같아 추가적인 작업이 가능할 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!