Leetcode #11 Container With Most Water

문제

인자인 height는 숫자로 이루어진 배열입니다.그래프로 생각한다면 y축의 값이고,
높이 값을 갖고 있습니다.

아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.

저 그래프에 물을 담는다고 생각하고, 물을 담을 수 있는 가장 넓은 면적의 값을 반환해주세요.

가정

배열의 길이는 2이상입니다.

나의 풀이

def get_max_area(height):
 	b = list(set(a))
 	b.sort(reverse=True)
 	print(b)
 	i = 0
 	c = abs(a.index(b[i])-a.index(b[i+1]))*b[i+1]
 	print(c)
  	< abs(a.index(b[i+1])*a.index(b[i+2]))*b[i+2]
 	for i in range(len(a)):
    	   result = abs(a.index(b[i+1])*a.index(b[i+2]))*b[i+2]
       		if result < abs(a.index(b[i+1])*a.index(b[i+2]))*b[i+2]:
        	   result = abs(a.index(b[i+1])*a.index(b[i+2]))*b[i+2]
      	 	else:
 #        print(result)
 # {0: 1, 1: 8, 2: 6, 3: 2, 4: 5, 5: 4, 6: 8, 7: 3, 8: 7}
 # index[1] (8) * index[8] (7)

• 면적값을 구해서 큰 면적으로 max()함수를 써서 업데이트하는 접근
• 인덱스와 상관 없이 높이 값이 제일 큰 수를 기준으로 잡고(예시로 따지면 8)
  높이 값이 낮은 순서대로 면적을 비교해 큰 값을 남기고 return
• 높이 값에 따라 인덱스 위치가 바뀌기 때문에 가로 길이를 구하는데 절댓값인 abs()를 사용하였다.

이 방법으로 시도해보다가 코드가 너무 복잡해져서 구현에 실패하였다. 더군다나 높이값이 중복이 되는 경우에는 기준값을 잡을 수가 없어서 로직 자체에 문제가 있다는 것을 깨달았다.
검색을 통해서 방법을 찾아보다가 Two Pointer라는 알고리즘을 알게 되었다.
즉 나의 첫번째 방법은 기준값을 높이가 제일 높은 값으로 잡았다면, 이 방법은 왼쪽 오른쪽 가로를 기준점으로 삼는 방법이었다.

수정한 풀이

def get_max_area(height):
  left = 0
  right = len(height) - 1
  result = (right-left)*min(height[left],height[right])
  while left < right:
    if height[left] <= height[right]:
      left += 1
    else:
      right -= 1
    result = max(result,(right-left)*min(height[left],height[right]))
  
  return result

• 왼쪽과 오른쪽의 pointer 변수를 선언한다. 각각 배열의 처음과 끝의 인덱스 값이다.
• result는 포인터를 바꿔가며 업데이트 해야할 면적의 값이다.
• 면적의 값은 그래프의 두 개의 막대기 중에서 낮은 값 기준으로 설정된다.
  그러므로 왼쪽 포인터와 오른쪽 포인터의 높이를 비교해서 오른쪽 포인터가 크면 낮은 쪽인 왼쪽의 포인터 값을 1 더하고, 반대면 오른쪽 포인터의 값을 1 뺀다.
• 포인터 값의 변동이 있을때마다 면적값인 result 를 업데이트 해준다.
• 최종적으로 왼쪽 포인터값이 오른쪽 포인터보다 크면 왼쪽과 오른쪽이 바뀐 비교를 중복해서 실행하는 것이므로 종료하고 result값을 반환한다.