백준 6549 히스토그램에서 가장 큰 사각형(python)

문제

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

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

---

정글에서 Week2 주제 중 분할정복에 해당하는 문제 였다. 분할 정복 접근법 말고도 여러 방법으로 풀어 봤는데, 그 중 스택을 사용한 방식이 인상적이였다. 그래서 스택으로 푼 풀이를 소개하려 한다. 먼저 효율성을 따지지 않고 완전 탐색 형식으로 원소 마다 앞뒤로 확장 하면서 값을 갱신해 나갈 수 있는데, 이렇게 하면 O(n^2) 의 시간 복잡도를 가지니 10만개 의 입력이 제한 시간 안에 통과 할 수 없다. 여기서 포인트는 높이가 낮을 수록 넓은 범위로 크기를 확장 할 수 있다는 점이다. 여기서 자료구조 스택을 사용하여 매번 최댓값을 갱신하지 않고 박스를 오름차순으로 쌓는 방법을 사용한다. 스택의 최상단의 값 보다 들어오는 값이 높다면  스택에 쌓아주고, 높이가 낮다면 더 낮은 높이의 사각형이 나올때 까지 pop하는 방식이다. 이런 형태의 스택을 모노톤 스택이라고 부른다. 한가지 방향(오름차순 또는 내림차순)을 갖는 스택이다. 

모노톤 스택을 사용하여 문제를 풀이하는 전체적인 방식은 다음과 같다.

 

1. 스택을 오름차순 형태로 만들 수 있게 값들을 넣어준다.
2. 그 중 작은 값이 들어오면 작은 값이 남을 때까지 stack을 비워주고 밑변값은 누적해서 넘겨준다.
3. 최종적으로 스택이 비워질 때 까지 반복한다.

스택은 파이썬의 리스트를 사용하여 구현했다.

스택에 들어갈 값은 높이와 밑변을 가지는 리스트로 구성하였다.

---

소스코드 

import sys
input = sys.stdin.readline


arr = []

while 1:
    f_arr = list(map(int, input().rstrip().split()))
    if f_arr[0] == 0:
        break
    ans = 0
    st = []
    arr = f_arr[1:]

    for val in arr:
        tmp = 0
        while len(st) != 0 and st[-1][0] > val:
            tmp += st[-1][1]  # 스택이 갖고 있던 밑변 값을 넘겨준다
            ans = max(ans, tmp * st[-1][0])
            st.pop()

        tmp += 1
        st.append([val, tmp])  # 높이와 밑변

    tmp = 0
    while len(st) != 0:  # 남은 값들 처리
        tmp += st[-1][1]
        ans = max(ans, tmp*st[-1][0])
        st.pop()

    print(ans)

추가 코드(분할 정복)

import sys
input = sys.stdin.readline
arr = []


def solve(lt, rt):
    global arr
    if lt == rt:
        return arr[lt]
    mid = (lt+rt)//2
    res = max(solve(lt, mid), solve(mid+1, rt))
    lo = mid
    hi = mid+1
    height = min(arr[lo], arr[hi])
    res = max(res, 2*height)

    while lt < lo or hi < rt:
        if hi < rt and (lt == lo or arr[lo-1] < arr[hi+1]):
            hi += 1
            height = min(height, arr[hi])
        else:
            lo -= 1
            height = min(height, arr[lo])

        res = max(res, height*(hi-lo+1))

    return res


while True:
    input_arr = list(map(int, input().rstrip().split()))
    if input_arr[0] == 0:
        break
    N = input_arr[0]
    arr = input_arr[1:]
    print(solve(0, N-1))