👏 key point
이 문제는 해당 막대 그래프에 연결된 모든 직사각형들의 넓이를 모두 순회(즉, 2중 for문을 사용한다. )하여 풀면 쉽게 풀 수 있다. 하지만 이 경우 시간복잡도가 O(n^2)이다. 입력크기가 1,000,000,000이기 때문에 이 방법은 적당하지 않다. 그렇다면 어떤 방법이 있을까???
먼저 분할정복이다.
우리는 입력받은 리스트를 반으로 쪼개면서 크기가 1이 될 때까지 분해하고 분해한 상태에서 분해된 리스트들의 값들을 비교하면서 합치는 방식이다.
그렇다면 위의 문제에서 어떻게 적용할 수 있을까??
우리가 최대 크기의 히스토그램 직사각형을 구할 수 있는 방법은 다음과 같다.
전체 히스토그램을 반으로 쪼갠 다음
1. 왼쪽에 있는 울타리의 최대의 직사각형
2. 오른쪽에 있는 울타리의 최대의 직사각형
3. 경계선에 걸처져 있는 울타리의 최대의 직사각형
위의 3가지를 고려하게 된다면 우리는 최대의 직사각형을 구할 수 있을 것이다.
예를 들어 3번 과정의 최대의 직사각형을 구하는 과정은 다음과 같다.
이때 이동할 왼쪽과 오른쪽의 히스토그램을 비교하여 큰 쪽을 먼저 지나 살펴보게 되고 높이는 이때까지 지나온 직사각형 중의 최솟값으로 설정하여 넓이를 구한다 따라서 넓이는
(r - l +1) * m_hei
이 때 1,2번은 3번의 과정을 재귀적으로 계산하여 구현할 수 있다.
🎂 코드
def srt(left, right):
mid = (left + right) // 2
if left == right:
return lst[left]
#l과 r은 이동할 왼쪽 오른쪽을 나타내는 변수
l, r = mid, mid+1
#3번 과정: 경계선에 걸쳐있는 2개의 직사각형의 넓이를 구한다.
m_hei = min(lst[l],lst[r])
m_size = 2 * m_hei
while left < l or r < right:
#l과 r이 가리키는 높이를 비교해서, 큰쪽으로 커진다.
if left == l:
r += 1
elif right == r:
l -= 1
else:
if lst[l-1] > lst[r+1]:
l -= 1
else:
r += 1
m_hei = min(m_hei,lst[l],lst[r])
m_size = max(m_size, m_hei * (r-l+1))
#왼쪽 분할, 오른쪽 분할, 그리고 접점을 포함하는 area중에서 제일 큰 값을 return
return max(srt(left, mid),srt(mid+1, right), m_size)
while True:
lst = list(map(int, input().split()))
if lst[0] == 0:
break
N = lst[0]
print(srt(1, N))코드 설명
1. 분할 과정
- 분할 하면서 경계선에 걸쳐있는 두 직사각형 넓이의 최댓값(왼쪽 오른쪽으로 넓혀가면서)을 구한다.
2. 합병 과정(merge)
-
이때까지 리스트들의 크기를 1로 만들어 분할했다면 이제는 다시 합쳐야 한다.
이처럼 srt(1,2) = srt(1,1)의 리턴값과 srt(2,2)의 리턴 값 그리고 m_size의 값 중 최댓값을 리턴한다. 이런 과정을 거쳐 결국 srt(1,7) 은 8을 리턴할 것이다.
