codekata10.
인자인 height는 숫자로 이루어진 배열입니다.그래프로 생각한다면 y축의 값이고, 높이 값을 갖고 있습니다.
아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.
저 그래프에 물을 담는다고 생각하고, 물을 담을 수 있는 가장 넓은 면적의 값을 반환해주세요.
문제파악
요구사항 : 배열의 숫자들과 index를 갖고 가장 넓은 면적의 값을 구해라.
제한사항 : 리스트의 길이는 2이상
인풋 : 숫자의 리스트
아웃풋 : 숫자
본질 : 각각의 숫자를 height로, 각각의 index 사이의 간격을 width로 구해라.
생각과정
- 반복문 안에서 가능한 모든 면적을 구한 다음, 가장 넓은 면적을 찾는다.
첫번째 방법
- 반복문 : 첫번째 높이로 만들 숫자.
- 반복문 : 두번째 높이로 만들 숫자.
- min : 두 높이 중에서 더 작은 값을 구한다. 물이 채워진다는건 결국 더 높은 값에선 넘치기 때문.
- 너비 : 두 값 사이의 index값 간격.
- 넓이 : 높이와 너비의 곱.
- 현재 반복문에서의 넓이가 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
Author And Source
이 문제에 관하여(codekata10.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wonseok2877/codekata10저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)