[백준/Python] 6549번 - 히스토그램에서 가장 큰 직사각형

 

문제

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

 

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

 

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

 

 

 

입력

 

입력은 테스트 케이스 여러 개로 이루어져 있다.

 

각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000)

 

그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다.

 

이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다.

 

모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

 

 

출력

 

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

 

풀이

 

이 문제는 가장 큰 직사각형의 넓이를 구하는 문제다.

만약 직사각형의 앞에서 부터 탐색을 한다면, 약 두가지로 경우를 구분할 수 있다.

 

예를 들어 첫 막대의 높이가 3이라고 가정하자.

다음에 나오는 막대가 높이가 같거나 높은 경우에는 높이가 3인 직사각형을 옆으로 더 확장할 수 있다.

만약 막대의 높이가 더 낮은 경우는 어떻게 될까?

 

다음에 나온 막대의 높이가 더 낮다면, 높이가 3인 직사각형을 더 이상 그릴 수 없게 된다. 

 

위의 두 경우를 이용하면, 이전의 높이보다 더 높은 막대가 나타나면 상관없지만, 높이가 더 낮은 사각형이 나타난다면 더이상 저장되어 있던 높이를 가진 직사각형을 그릴 수 없다는 사실을 알 수 있다.

 

이를 이용하면 내가 그릴 수 있는 직사각형의 크기를 O(n) 시간으로 알 수 있다.

 

이제 풀이 방법을 예를 들어 설명하겠다

 

높이가 a, b, c 순서대로 커지는 막대가 있다고 가정하자.

다음에 d라는 막대를 탐색하는데 여기서 아래와 같이 경우를 나눌 수 있다.

 

[d막대가 c막대의 높이와 같거나 높은 경우]

 

1. d막대의 높이가 c보다 크다면, d의 높이를 가진 직사각형은 d부터 그릴 수 있으므로, 높이를 d로 바꾸고 직사각형의 시작점을 d로 바꾼다.

2. d막대의 높이가 c와 같다면, d의 높이를 가진 직사각형은 c부터 그릴 수 있으므로, 높이와 시작점을 그대로 둔다.

 

 

[d막대가 c막대의 높이보다 낮은 경우]

 

1. 더 이상 c높이의 직사각형을 그릴 수 없으므로, c높이를 가진 직사각형의 가장 긴 밑변은 시작점(c)부터 현재 d막대까지 그릴 수 있다.

2. c 높이의 직사각형의 크기를 비교해 가장 큰 직사각형을 갱신한다.

3. 이제 c 이전의 막대인 b와 d의 높이를 비교해 b높이의 직사각형을 더 그릴 수 있는지 확인한다.

4. 위 과정을 반복한다.

 

이제 위 코드를 구현하면 되는데 이때 이용하면 좋은 자료구조가 stack이다.

 

마지막으로 탐색한 막대와 다음 막대를 비교하는 과정이 후입선출의 구조와 비슷하기 때문이다.

 

먼저 stack이 비어있다면 블럭을 넣고 만약 stack이 비어있지 않을 경우 stack의 마지막에 기록된 높이를 현재 블럭의 높이와 비교한다.

 

만약 현재 쌓여있는 블록의 높이가 stack의 마지막에 기록된 높이보다 높으면 stack에 추가한다.

 

만약 작다면 stack에서 제거한 후 stack에 저장해둔 가로 위치부터 현재 블럭의 가로 위치를 뺀다음 stack에서 제거한 정보의 세로 높이를 곱해 최대값을 비교한다.

 

stack에 쌓을 때 이전 stack보다 높을 경우만 stack에 추가하며 계산하기 때문에 n개의 블럭을 비교 하는 것만으로 히스토그램에서 가장 큰 직사각형이 무엇인지 파악할 수 있다.

​

여기서 주의할 점은 이전에 쌓인 스택보다 더 작은 높이의 블럭이 왔을 때, 시작되는 값을 수정해주어야 한다.

 

현재 블럭의 높이가 더 작으므로 이전 위치부터 더 큰 직사각형을 그릴 수 있기 때문이다.

 

 

 

Code

 

 

import sys
input=sys.stdin.readline
def histo(lst):
    recnt=0
    stack=[]
    stack_len=0
    for i in range(1,lst[0]+2):
        if stack_len==0:
            stack.append([i,lst[i]])
            stack_len+=1
        else:
            stack_pop =[i,0]
            while True:
                if stack_len==0:
                    stack.append([stack_pop[0], lst[i]])
                    stack_len += 1
                    break
                stack_now=stack[stack_len-1]
                if stack_now[1]<lst[i]:
                    stack.append([stack_pop[0], lst[i]])
                    stack_len+=1
                    break
                elif stack_now[1]>lst[i]:
                    stack_pop=stack.pop()
                    stack_len-=1
                    ans=(i-stack_pop[0])*stack_pop[1]
                    if recnt<ans:
                        recnt=ans
                else:
                    break
    return recnt
while True:
    lst=list(map(int,input().split()))
    lst.append(0)
    if lst[0]==0:
        break
    print(histo(lst))

 

---

 

 

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