첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.
입력 예시
7
2
1
4
5
1
3
3
출력 예시
8
풀이
크게 내가 푼 분할 정복과, 그리고 스택을 이용한 풀이 두 가지가 있다고 한다. 스택을 이용한 풀이는 생각지도 못했다...!(사실 비슷한 문제를 전에 본 적이 있던 것 같은데, 잊고 너어갔다. 그 때 기록해두지 못한 자신을 반성하자...)
단순히 모든 히스토그램의 높이에 따라 최대 면적을 구해본다면 시간복잡도가 O(N^2)이 된다. 즉 절대 제한시간 내에 풀이가 불가능해진다. 따라서 O(NlogN)의 시간복잡도가 소요되는 분할정복을 이용해 볼 필요가 있다.
시작 좌표가 start, 끝 좌표가 end인 구간 [start, end]의 최대 면적을 구하는 방법을 생각해보자. 이 때, 가운데 좌표 mid = (start + end) // 2를 미리 정의한다.
우선 초기항부터. start == end인 경우 그 위치의 좌표가 값이 된다.
그렇지 않은 경우(start < end) 다음 세 가지 경우가 존재할 수 있다.
왼쪽 구간 [start, mid] 에 최대 면적이 존재할 경우 : 왼쪽 구간의 최대 면적을 재귀적으로 구해보면 된다.
오른쪽 구간[mid+1, end] 에 최대 면적이 존재할 경우 : 이 역시, 오른쪽 구간의 최대 면적을 재귀적으로 구해보면 된다.
왼쪽 구간과 오른쪽 구간에 걸쳐 최대 면적이 존재할 경우 : 이게 핵심이 되겠다. 이 경우는 조금 생각을 다르게 접근해 볼 필요가 있다. 왼쪽 구간과 오른쪽 구간에 걸친다는 조건이 전제되므로, 왼쪽 구간의 오른쪽 끝(mid)과 오른쪽 구간의 왼쪽 끝(mid+1)은 반드시 최대 면적에 포함되어야 한다. 즉 이 좌우 좌표를 기준으로 구간 좌표를 넓혀가며 최대 면적을 찾으면 된다. 구간 좌표가 넓어질 때 그 구간의 면적은 (구간의 높이 최소값) * (구간의 너비)가 된다. 이 때 최대 시간복잡도는 O( end - start )가 되겠다. 즉 상수 시간이 증가한다고 볼 수 있다.
풀이 코드
import sys
input = sys.stdin.readline
N = int(input())
num_list = [int(input()) for _ in range(N)]
def divide_and_conquer(start, end) :
if start == end :
return num_list[start]
mid = (start + end) // 2
left_val = divide_and_conquer(start, mid)
right_val = divide_and_conquer(mid+1, end)
h = min(num_list[mid:mid+2])
mid_val = h*2
l, r = mid, mid+1
while start < l or r < end :
if r == end :
l -= 1
h = min(h, num_list[l])
elif l == start :
r += 1
h = min(h, num_list[r])
elif num_list[l-1] < num_list[r+1] :
r += 1
h = min(h, num_list[r])
else :
l -= 1
h = min(h, num_list[l])
mid_val = max(mid_val, h*(r-l+1))
return max(left_val, right_val, mid_val)
print(divide_and_conquer(0, len(num_list)-1))
