문제

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

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

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

가정

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

나의 풀이

가장 큰 면적을 구해야 하기 때문에, 하나하나 그래프의 높이 만큼 만들수 있는 최대의 높이를 구해야 한다고 생각했다.

• 그래프 처음부터 끝까지 계산할 수 있는 모든 면적의 경우를 따져야 하기 때문에, 2중 for문으로 돌린다.
• 사각형의 면적은 가로 * 세로이므로, x축을 가로라고 가정한다.
• 바깥 for문의 i를 거리의 start지점, 안쪽 for문의 j를 end지점으로 두고, 두 거리의 차를 면적의 가로로 계산한다.
  작은수에서 큰수를 빼면 마이너스가 나오기에 마이너스일 경우, -1을 곱해준다.
• 주어지는 세로축은 캔들의 가장 높은 지점에서 수평선을 그어 만나는 다른 캔들이 있다면 두 캔들 중, 높이가 작은 부분을 세로로 계산한다.
• 위 계산 과정을 거쳐 max값과 계속 비교하여, max보다 크다면 그 값이 최대값이 되기 때문에, max의 값을 갱신한다.

def calc_distance(num1, num2):
  dis = num1 - num2
  return dis * -1 if dis < 0 else dis

def chk_num(num1, num2):
  return num1 if num1 < num2 else num2

def get_max_area(height):
  max = 0

  for i in range(0, len(height)):
    for j in range(0, len(height)):
      if i == j: continue
      if max < calc_distance(i, j) * chk_num(height[i], height[j]):
        max = calc_distance(i, j) * chk_num(height[i], height[j])

  return max

수정

위의 코드는 한번 계산했던 걸 다시 계산하는 중복이 발생 하는데 중복을 제외할 수 없을까 생각하다 바깥 for문의 i를 안쪽 for문의 start지점으로 받아 주면 지나 왔던 캔들을 다시 계산 안해도 되고 마이너스 거리도 생각 안해도 된다는 점이 떠올라서 아래와 같이 소스코드를 수정 했다.

def calc_distance(num1, num2):
  return num2 - num1

def chk_num(num1, num2):
  return num1 if num1 < num2 else num2

def get_max_area(height):
  max = 0

  for i in range(0, len(height)):
    for j in range(i, len(height)):
      if i == j: continue
      if max < calc_distance(i, j) * chk_num(height[i], height[j]):
        max = calc_distance(i, j) * chk_num(height[i], height[j])

  return max