문제

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

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

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

가정

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

Solution

내가 처음으로 작성한 코드는 아래와 같다.

def get_max_area(height):
  list=[]
  for i in range(len(height)):
    for j in range(len(height)):
      if j>i:
        list.append((j-i)*min(height[i],height[j]))
  return max(list)

만약 (x1, y1), (x2, y2)라는 좌표로 생각을 해본다면,

물의 면적은 (x2-x1) * (y1,y2 중 의 최소값)으로 나타낼 수 있다.

빈 리스트를 만들어서, 리스트의 길이만큼 이중루프를 돌려주고

(j-i)를 가로, min(height[i],height[j])를 세로로 하여 모든 면적의 값을 계산한 다음,

그 최대값을 return하는 식으로 해결하였다.

하지만 이렇게 하면 height라는 리스트의 길이가 길다면,

그 길이의 제곱만큼 연산을 해야한다는 문제점이 있다.

이 문제를 해결하기 위해 양쪽에서 접근한다는 해결법이 있다.

(내가 해결한 건 아님;)

def get_max_area(height):
  L = 0 # 처음 index
  R = len(height) - 1 # 가장 끝 index
  res = 0 # 초기 넓이
  while L < R: # 왼쪽 index가 오른쪽 index보다 작을때까지
    area = (R - L) * min(height[L], height[R]) # 넓이를 구하여 값을 저장
    res = max(area,res) # 기존 넓이와 비교하여 값을 저장
    if height[L] < height[R]: # 왼쪽 index 높이가 오른쪽 index 높이보다 작다면
      L += 1 # 다음 왼쪽 index와 비교
    else:
      R -= 1 # 그전 오른쪽 index와 비교
  return res

이렇게 되면, 리스트의 길이만큼만 값을 구하여 비교하면 해결된다.