[Algorithm] 2주차 5번 문제

김상웅·2022년 6월 17일
0

[알고리즘]

목록 보기
8/18

📌 문제


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

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

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

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



✅ 풀이


문제 분석에 꽤 많은 시간을 보낸 것 같습니다.

우선 물을 담을 수 있는 그릇의 높이는 배열의 index 값을 가리킵니다.
너비는 배열의 index의 값이 되겠죠?

물을 최대한 많이 담기 위해서는 높이와 너비를 곱한 값이 가장 커야합니다.

이중 for loop를 통해 배열의 모든 원소를 높이로, index의 차이를 너비로 지정해주어 그 둘을 곱한 값이 가장 큰 값을 찾아주면 됩니다.

풀이는 아래와 같습니다:

def answer(height) :
	result = []
    
    for i in range(len(height)) :
    	for j in range(len(height)) :
        	min_height = min(height[i], height[j])
            width      = abs(j-i)
            v          = min_height * max_width
            result.append(V)
	return max(result)
profile
누구나 이해할 수 있도록

0개의 댓글