[리트코드] 1130. Minimum Cost Tree From Leaf Values / Javascript

문제주소 : https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/

Minimum Cost Tree From Leaf Values - LeetCode

---

<문제 설명>

Given an array arr of positive integers, consider all binary trees such that:

• Each node has either 0 or 2 children;
• The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
• The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

A node is a leaf if and only if it has zero children.

 

Example 1:

Input: arr = [6,2,4] Output: 32 Explanation: There are two possible trees shown. The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.

Example 2:

Input: arr = [4,11] Output: 44

 

Constraints:

• 2 <= arr.length <= 40
• 1 <= arr[i] <= 15
• It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).

 

<풀이법>

▒ 한줄 개념: Greedy, Bottom-up ▒ 

리프노드를 시작으로 그리디하게 바텀업 방식으로 계산해나가는 문제입니다.

구현방법은 다음과 같습니다.

(반복)

  1. 연속된 두 리프노드의 곱 중, 최소값을 구함

  2. 최소값을 answer에 더함

  3. 연속된 두 리프노드 중, 더 작은 값 삭제

 

arr = [6, 2, 4, 3]일 때, 예시를 들어보겠습니다.

 

1. 연속된 두 리프노드의 곱 중, 최소값을 구함

i = 0,
min = 6 * 2 = 12

i = 1,
min = 2 * 4 = 8

i = 2,
min = 4 * 3 = 12

  이 중 값이 최소인 경우는 i = 1, val = 8일 때 입니다. 

 

2. 최소값을 answer에 더함

  위에서 구한 최소값이 8이므로, answer += 8 을 해줍니다.

 

3. 연속된 두 리프노드 중, 더 작은 값 삭제

  더 작은 값을 삭제해주는 이유는, 모든 부모 노드는 자신의 값을 계산할 때 왼쪽 서브트리에서 가장 큰 리프노드, 오른쪽 서브트리에서 가장 큰 리프노드만을 참조하기 때문입니다. 따라서 한번 계산 시에 더 작았던 리프노드 값은, 다시는 사용할 일이 없게 됩니다. 

 결과적으로 이번 예시에서는, 2 와 4 중 더 작은 2 값이 arr에서 삭제됩니다.

 

이렇게 1, 2, 3 번을 거친 후의 상태는 아래와 같게 됩니다.

arr = [6, 4, 3]

answer = 8

 

동일한 방식으로 arr에서 단 하나의 리프노드만 남을 때까지 반복해주게 되면, 정답을 구할 수 있게 됩니다.

 

<코드(Javascript)>

/**
 * @param {number[]} arr
 * @return {number}
 */
var mctFromLeafValues = function(arr) {
    let answer = 0;
    
    while(arr.length > 1){
        let minIdx = 0;
        let minVal = 226; 
        for(let i = 0; i < arr.length - 1; i++){
            if(arr[i] * arr[i + 1] < minVal){
                minIdx = i;
                minVal = arr[i] * arr[i + 1];
            }
        }
        answer += minVal;
        if(arr[minIdx] < arr[minIdx + 1]){
            arr.splice(minIdx, 1);
        }else{
            arr.splice(minIdx + 1, 1);
        }
    }

    return answer;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest