[파이썬 | BOJ | 6549] 히스토그램에서 가장 큰 직사각형

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

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이 하나 주어진다.

출력

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

풀이

처음 생각한 풀이는, 왼쪽에서 오른쪽으로 탐색해 가면서, 어떤 n번째 위치에서 맨 왼쪽까지 사각형 길이 중 가잔 큰것을 탐색해 나가면서, 가장 큰 사각형을 저장하는 것이다. 하지만 이는 O(n^2)의 시간복잡도를 지녀서 시간초과를 해결하기가 어려웠다. 따라서 시간 초과를 해결하기 위한 근본적인 방법은, 이분 탐색으로 왼쪽 오른쪽에서 가장 큰 사각형을 찾고, 접합부를 포함한 사각형의 크기도 고려해서 총 세가지를 비교해서 최대값을 구하는 것이다.

 

접합부를 포함한 사각형의 크기중에서 최대값을 고르는 것이기때문에, 왼쪽과 오른쪽의 경계를 점점 증가시켜 나가면서, 사각형의 크기가 커질 수 있는 방향으로 증가한다.