11. Container With Most Water

문제 §

height가 포함된 n Length의 array가 주어짐. 이 array의 조합을 통해 최대 volume 구하기

Input: height = [1,1] Output: 1

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49

제한조건 §

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

아이디어 §

• array의 가장 끝부터 줄여나감
  • 양쪽 끝 height를 비교해 작은 쪽을 가운데로 모음
• 모든 array item을 Traverse해서 결과 값을 Return

풀이 §

class Solution:
 
def maxArea(self, height: List[int]) -> int:
 
self.arr = height
 
self.len = len(height)
 
return self.calcHelper(0,self.len-1)
 
  
 
def calcHelper(self,cur_max:int,right,left=0) -> int:
 
if left >= right:
 
return cur_max
 
height = min(self.arr[left],self.arr[right])
 
cur_volume = height * (right-left)
 
  
 
cur_max = max(cur_max,cur_volume)
 
  
 
if self.arr[left] < self.arr[right]:
 
return self.calcHelper(cur_max,right,left+1)
 
else:
 
return self.calcHelper(cur_max,right-1,left)

후기 §

공부한 내용을 활용해보고 싶었다. 그래서 tail recursion을 활용해보려했다. LeetCode의 대부분 문제들이 helper function은 안쓴다. 아마 memory 문제 등으로 인한 것으로 보인다. 일단 최대한 tail recursion을 활용해 보는 방법으로

#tailrecursion#leetcode#greedyalgorithm#twopointer#array#python