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

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

문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

while True:
    number = list(map(int,input().split()))
    num = number[0]
    stack = []
    ans = 0
    if num==0:
        break
    number=number[1:]
    for i in range(num):
        idx = i
        while stack and stack[-1][0] >= number[i]:
            ans = max(ans,(i-stack[-1][1])*stack[-1][0])
            idx = stack[-1][1]
            stack.pop()
        stack.append([number[i],idx])
    while stack:
        ans = max(ans,(num - stack[-1][1])*stack[-1][0])
        stack.pop()
    print(ans)

이번 문제도 스택으로 해결 할 수 있습니다. 앞에서 부터 하나씩 봅시다.

첫번째 테스트 케이스인 7 2 1 4 5 1 3 3 을 봅시다.

일단 7은 숫자의 개수이고 나머지 배열을 분리해서 저장을 하고 stack와 ans를 초기화 합니다.

idx는 첫번째니 0으로 초기화를 합시다. 그리고 스택에는 아직 아무것도 들어있지 않으니

[2,0]이 들어가 있습니다.

그 다음으로 1을 넣었습니다. while 조건에 맞으니 봅시다.

ans는 0과 2를 비교해서 2가 더 크니 2로 갱신을 합시다. 첫번째 블럭 크기는 2가 됩니다.

idx는 0이 됩니다. 그리고 제거를 합니다.

스텍에는 [1,0]이 들어가 있습니다.

다음으로 4를 넣었습니다. while문의 조건을 만족하지 못해서 그대로 스택에 넣습니다. 그렇게 5까지 들어갑니다.

[[1, 0], [4, 2], [5, 3]]

이제 1을 넣게 됩니다. 조건을 따져봅시다.

i는 현재 4입니다. (4-3)*5 = 5가 됩니다. 2보다는 5가 크니 ans는 5로 갱신을 합니다.

idx는 3이 되고 pop을 합니다. 여전히 4는 1보다 크니 조건을 만족합니다.

i는 아직 그대로 4입니다. 스택에 제일 위에는 4,2가 들어 있습니다.

2*4 = 8이 되고 ans는 8로 그리고 idx는 2로 갱신하고 빠져나옵니다.

이렇게 끝까지 돌았으나 스택이 비어있는지 확인을 합니다.

그러니까 위의 알고리즘은 이렇게 생각 하시면 됩니다.

일단 숫자를 쌓아 갑니다. 높은 순서로 말이지요 1..2..3..4.. 그러다가 1같이 마지막에 올라온 4보다 작은 숫자가 들어오면 계산을 해봅니다. 첫번째 4만 봅시다. 인덱스의 길이는 1이고 넓이는 4가 됩니다.

한칸 빼봅시다. 인덱스의 길이는 2이고 높이는 3이니 넓이는 6이 됩니다.

비교할 조건인 1에 다다를때까지 비교를 합니다. 인덱스의 길이는 3 높이는 2 넓이는 6

그리고 1까지 가면 넓이는 4가 되겠네요

이런식으로 제일 넓은 넓이를 연산합니다.

위의 것으로 다시 설명을 하면 2가 들어오고난 다음 1이 들어 왔습니다. 2에서 넓이는 2가 되고 더 이상 스택에 남아 있는 것이 없으니 뺍시다. 그리고 4, 5 가 들어 왔습니다.

그러면 5에서는 너비가 51 = 5가 되고 한칸 뺀 4에서는 42 = 8 최대 너비가 됩니다.

굉장히 어렵게 생각했는데… 결국 지난번 탑에서 높고 낮음의 아이디어를 응용하면 되는 듯 합니다.

그래도 지금까지 푼 스택 문제중에서 제일 난이도 있다고 생각했는데 역시 플래티넘 수준의 문제였네요