JavaScript:: 그래프의 최대 넓이 값 구하기

[JavaScript] 그래프의 최대 넓이 값 구하기

문제

'인자'인 height는 숫자로 이루어진 배열입니다.
그래프로 생각한다면 y축의 값이고, 높이 값을 갖고 있습니다.
아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.

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

• 가정 : 배열의 길이는 2이상입니다.

해결 과정

우리가 해결해야 할 문제는 아래와 같다.

1. 각 배열의 요소를 돌아가며 다른 배열의 요소의 값과 함께 넓이를 구한다.
2. 넓이를 구할 때 두 수를 비교하는데, 최소값을 통해 높이 값을 구한다.
3. 두 요소의 인덱스 값을 비교해 가로값을 구한다.
4. 모든 경우의 수로 담긴 넓이의 값을 비교하여 큰 수부터 내림차순으로 배열을 정리한다.
5. 배열 중 가장 큰 수를 반환한다.

해결 과정의 코드는 아래와 같다.

1번 과정

function getMaxArea(height) {
    let value = [];
    for (let i=0; i < height.length; i++) {
        for(let z=height.length-1; z>i; z--) {
          // 이중 for문을 이용해 두 수를 비교할 수 있도록 한다.
        }
    }
}

첫번 째 for문은 배열의 첫자리 수 부터,
두번 쨰 for문은 배열의 뒷자리 수 부터 이동하여
(배열의 뒷자리 수 부터 이동하던, 배열의 앞자리 수 부터 이동하던 상관은 없다)

배열에서 구해질 수 있는 넓이의 모든 경우의 수 값을 구한다.

2, 3번 과정

function getMaxArea(height) {
    let value = [];
    for (let i=0; i < height.length; i++) {
        for(let z=height.length-1; z>i; z--) {
          value.push(Math.min(height[i], height[z]) * (z-i))
        }
    }
}

Math.min(height[i], height[z]) 가 두 수 중의 최소값을 구해 나온 총 넓이의 높이 값이다.

(z - i) 는 두 수의 인덱스 값을 비교하여 넓이의 가로 길이를 구하기 위함이다.

이렇게 구해진 넓이의 세로, 가로 길이를 서로 곱하여 나온 넓이의 값을 value라는 배열에 저장한다.

4번 과정

function getMaxArea(height) {
    let value = [];
    for (let i=0; i < height.length; i++) {
        for(let z=height.length-1; z>i; z--) {
          value.push(Math.min(height[i], height[z]) * (z-i))
        }
    }
    value.sort(function(a,b) {
        return b - a
    })
    console.log(value);
}
getMaxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);
// [49, 40, 36, 24, 20, 18, 16, 15, 15, 14, 12, 12, 10, 10, 10, 9, 8, 8, 7, 6, 6, 6, 6, 5, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1]

이중 for문을 이용해 구한 각각의 경우의 수들을 담은 value라는 이름을 가진 변수 배열에 sort 함수를 이용하여 각 값들을 큰 수 부터 내림차순으로 정렬한다.

( sort 함수의 매개변수인 a,b는 각각 a는 뒷자리, b는 앞자리이며 음수가 return 될 경우, 각 인자의 위치가 바뀐다.)

5번 과정

function getMaxArea(height) {
    let value = [];
    for (let i=0; i < height.length; i++) {
        for(let z=height.length-1; z>i; z--) {
          value.push(Math.min(height[i], height[z]) * (z-i))
        }
    }
    value.sort(function(a,b) {
        return b - a
    })
    return value.shift();
}
getMaxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);
// 49

shift 메소드를 이용해 내림차순으로 정의된 value 변수의 배열에서 가장 첫번째 값, 즉 가장 넓이가 큰 값을 반환한다.

문제 해결 완료👏🏻