Algorithm - list elements comparison

이주명·2021년 11월 28일
0

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

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

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

위의 배열을 담은 함수의 리턴값은 49가 된다.

이 문제는 결국 리스트 안에 요소 2개를 골라
가로길이 : 두 요소의 사이의 인덱스값 차
세로길이 : 두 요소의 값 중 작은값

넓이를 구해 가장 큰 값을 리턴 하라는 것이다.

방법 1 : 앞에서 부터 차례대로 비교하기

def get_max_area(height) :

   max_result = 0
   tem_result = 0
  
   for i in range(0, len(height)) :
     for j in range(i+1, len(height)) :
       if height[i] > height[j] :
         tem_result =  height[j] * (j - i)
       else :
         tem_result = height[i]  * (j - i)
       if tem_result > max_result :
         max_result = tem_result
   return max_result

나는 처음 방법으로 하나씩 앞에서부터 다 비교하는 식으로 코드를 만들었다. 이는 이중for문을 사용했고 그렇게 좋은 방법은 아니다.

첫 번째 인자를 꺼내서 그와 나머지 인자들을 이용해 넓이를 구한뒤 더 큰 넓이를 변수에 저장하는 식으로 했다.

  1. 반복 횟수 ++
  2. 시간 ++

방법 2 : 앞과 뒤에서 비교하기

def get_max_area(height) :
    left = 0 
    right = len(height) -1
    result = 0
    while left < right :
        if result < min(height[right], height[left])*(right - left) :
            result =  min(height[right], height[left])*(right - left) 
        if height[right] > height[left] :
            left = left + 1
        else :
            right =right - 1
    return result 

두번째 방법은 왼쪽과 오른쪽에서 비교를 시작하며 가운대로 모이는 형식의 비교이다. 이 방법이 훨씬 시간, 반복 효율적이다.
왼쪽과 오른쪽의 높이를 비교해서 보다 작은 높이를 가진 한쪽을 한칸 옮기는 형식이다.

  1. 시간 --
  2. 반복 횟수 --

이 밖에 더 좋은 방법이 있으면 알려주세요!

profile
oh yeah

0개의 댓글