Code Kata | day10 get_max_area

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

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

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

☑️ 0차 (fail)

• 높이(y)를 기준으로 만들 수 있는 넓이 중 최대 넓이를 max 에 저장

def get_max_area(height):
  max_area=0
  for y in range(1, max(height)+1):
    lst = [height.index(a) for a in height if a>=y]
    area = y * (lst[-1]-lst[0])
    if area>=max_area:
      max_area = area
  return max_area

리뷰

• index 메소드가 중복값에 대해 같은 인덱스를 반환하는 문제 발생
  예 ) [1,1,1] 내의 모든 1이 첫번째1의 인덱스인 0을 반환

☑️ 1차 (pass)

def get_max_area2(height):
  max_area=0
  for y in range(1, max(height)+1):
    lst=[a for a,b in enumerate(height)if b>=y]
    area = y * (lst[-1]-lst[0])
    max_area = max(max_area, area)
  return max_area

수정

• 좌표 형식으로 만들기 위해서 index - > enumerate 수정
  예) height.index(a) -> a foro a,b in enumerate(height)
• 최대값을 저장하는 로직 한줄로 수정
  예)

#수정 전
if area >= max_area:
    max_area = area
   
#수정 후
max_area = max(max_area, area)

☑️ 2차 (pass)

• 원 출처에서 따봉을 제일 많이 받은 코드를 공수해왔다..!!

def get_max_area3(height):
    L, R, width, res = 0, len(height) - 1, len(height) - 1, 0
    for w in range(width, 0, -1):
        if height[L] < height[R]:
            res, L = max(res, height[L] * w), L + 1
        else:
            res, R = max(res, height[R] * w), R - 1
    return res 

Review

• 원리 : 최대 가로길이에서 시작해서 가로길이를 한칸씩(height길이를 1씩) 줄여나간다.
  그 때 만들 수 있는 넓이(가로길이 * 더 짧은 높이) 를 구해서 최대값을 저장, 반환한다.
• 더 적은 경우의 수로 답을 도출할 수 있는 원리를 깨우치는 게 중요한 것 같다. 몇시간씩 머리를 싸맨다고 아이디어가 떠오른다고 장담할 수도 없고, , 그냥 여러가지 문제를 많이 접해보는 게 답인 것 같다.