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

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

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

문제파악

요구사항 : 배열의 숫자들과 index를 갖고 가장 넓은 면적의 값을 구해라.

제한사항 : 리스트의 길이는 2이상

인풋 : 숫자의 리스트

아웃풋 : 숫자

본질 : 각각의 숫자를 height로, 각각의 index 사이의 간격을 width로 구해라.

생각과정

1. 반복문 안에서 가능한 모든 면적을 구한 다음, 가장 넓은 면적을 찾는다.

첫번째 방법

1. 반복문 : 첫번째 높이로 만들 숫자.
2. 반복문 : 두번째 높이로 만들 숫자.
3. min : 두 높이 중에서 더 작은 값을 구한다. 물이 채워진다는건 결국 더 높은 값에선 넘치기 때문.
4. 너비 : 두 값 사이의 index값 간격.
5. 넓이 : 높이와 너비의 곱.
6. 현재 반복문에서의 넓이가 result변수의 값보다 크다면, result에 할당한다.

def get_max_area(height):
  print(height)
  result = 0
  for i1, h1 in enumerate(height):
    for i2, h2 in enumerate(height):
      min_h = min(h1, h2)
      width = i2 - i1
      area = min_h * width
      if area > result:
        result = area
  return result

두번째 방법

by 예랑님.

첫번째 방법과 접근은 같지만, 반복문의 횟수가 줄어들었다.
range에서 i+1 인덱스부터 시작함으로써, 이미 비교한 값들끼리는 반복문을 실행하지 않는다.

def get_max_area(height):
 result = 0

 for i in range(0, len(height)):
   h1 = height[i]
   for j in range(i+1, len(height)):
     h2 = height[j]
     area = min(h1, h2) * abs(i-j)

     if area > result:
       result = area

 return result

abs함수를 쓰는 대신, j에서 i를 빼도 된다. 어차피 i의 다음 인덱스이니까.

세번째 방법

by 준영님 동명님.

각각의 height(바)에서 뽕을 뽑은 다음 index를 옮겨간다고 생각하면 편하다.

def get_max_area(height):
  result = 0
  left, right = 0, len(height) - 1
  main_height = 0

  while left < right :

    if main_height >= height[left]:
      left += 1

    if main_height >= height[right]:
      right -= 1
    
    main_height = min(height[left], height[right])
    area_as = abs(left-right) * main_height

    if area_as > result:
      result = area_as
  
  return result