가장 큰 면적 구하기

정수로 이루어진 배열이 있다. 그래프로 생각한다면 y축은 높이값이고 각 인덱스는 두 인자 간 넓이값을 구하는 기준이 된다. 아래의 그래프는 [1,8,6,2,5,4,8,7] 의 이미지이다.
그래프에 물을 담는다고 생각하고, 물이 담길 수 있는 가장 넒은 면적을 구하라.

분석

위 문제가 요구하는 것은 배열에 있는 인자들의 값이 높이, 그리고 인자들간 index 차이를 넓이라 보고 나올 수 있는 가장 큰 면적(높이 * 넓이)을 구하는 것이다. 위 그림은 49를 가장 큰 면적이라는 결론을 보여주고 있다

풀이

def get_max_area(height):
	l	= 0
    	r	= len(height)-1
    	area	= 0

	while l < r:
    		area = max(area, min(height[l], height[r]) * (r-l))
        	if height[l] < height[r]:
            		l += 1
            	else:
                	r -= 1

	return area

print(get_max_area([1,8,6,2,5,4,8,3,7]))

해설

주어진 배열의 첫번째 인자와 마지막 인자를 시작으로 두 인자 중 높이가 낮은 값과 인자 간 차를 넓이로 하여 면적을 구한다. 구한 면적은 기존에 저장한 면적보다 크면 갱신한다.
다음 면적을 구할때는 높이가 낮았던 인자의 옆에 있는 인자를 대상으로 하도록 타겟을 변경하는 방법으로 반복 계산한다.