-
https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
트리 자료구조에 얽매여서 생각하면 문제가 어려워진다.
리프노드와 논리프노드를 제외한다면, 트리 개념이 그닥 필요하지 않은 문제. 핵심은 큰 숫자의 곱셈 횟수를 최소화 하는 것 이다.
var mctFromLeafValuesGreedy = function(arr) { let cost = 0; while (arr.length>1) { let minProduct = Number.MAX_VALUE; let minId = -1; for (let i=0;i<arr.length-1;i++) { let curProduct = arr[i] * arr[i+1]; if (curProduct < minProduct) { minProduct = curProduct; minId = arr[i]<arr[i+1]?i:i+1; } } cost+=minProduct; arr.splice(minId, 1); } return cost; }
'알고리즘 > 리트코드' 카테고리의 다른 글
34. Find First and Last Position of Element in Sorted Array (0) 2021.06.16 1314. Matrix Block Sum (0) 2021.06.01 1043. Partition Array for Maximum Sum (0) 2021.05.27 542. 01 Matrix (0) 2021.05.27 210. Course Schedule II (0) 2021.05.24 댓글