29Dec2019 TIL

Today I learned : 

• toy 07 (Tree Depth-first Search Selection)
• toy 08 (Largest Product of Three)

---

Tree Depth-first Search Selection 의 구현

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking. (출처 : 위키피디아)

Tree.prototype.DFSelect = function (filter) {};구조로 되어 있다. callback인 filter는 value와 depth를 parameters 로 가진다. 재귀를 사용하여 푼 결과는 다음과 같다. 

Tree.prototype.DFSelct = function (filter) {
  let result = [];
  function recurse (node, depth) {
    depth = depth || 0; 	// depth 값이 있다면, 그 값을 사용하고, 아니면 0.
  	!!filter(node.value, depth) ? result.push(filter(node.value)) : result;
    
    for(let el of node.children) {
      recurse (el, depth+1);
    }
  }
  recurse(this);
  return result;
};

 

그러나 이 블로거에 따르면, 엔지니어로서 도전을 하고 싶다면, pure 한 함수적 로직 마인드를 기르기 위한 훈련도 필요.

In many cases it may not make a huge difference, like in a toy problem solution. But toy problems are exercises, and exercising your pure functional muscles can have advantages for you as an engineer. Pure functions don’t modify any aspect of their environment outside of their own scope.

 

Tree.prototype.DFSelct = function (filter) {
  depth = depth || 0;
  let rootSelection = filter(this.value, depth) ? [this.value] : [];
  let childSelections = this.children.map(function(child){
    return child.DFSelect(filter, depth + 1);
  });
  return [].concat.apply(rootSelection, childSelections);
};

 

Why use [].concat.apply instead of rootSelection.concat(childSelections)?
Remember that a new rootSelection variable is being declared each time DFSelect is called. This could lead to hundreds of independent variables, each in their own scope. In order to bring this long chain of arrays together, we have to concatenate them into one array. Squint at the final return statement and you can maybe see it not as one short line of code but as a potentially very long chain of strung-together scopes, which get compressed back together when the recursion runs through the entire tree.

 

---

Largest Product of Three 구현

나의 생각 : 양수의 큰 수를 만들기 위해선 : +++, +-- 의 각각의 최대값을 비교한다. 음수만 있는 경우, 음수의 제일 작은 수를 택한다. 나의 코드는 다음과 같다. 코드 변수 많음 주의. 복잡함 주의! 

 

var largestProductOfThree = function(array) {
  if (array.length === 3) {
    return array.reduce((a, b) => a * b);
  }
  if (array.length > 3) {
    let subPlus = 0,
      subMinus = 0;
    let minus = array.filter(a => a < 0).sort((a, b) => a - b);
    let plus = array.filter(a => a > 0).sort((a, b) => a - b);
    let threePlus = plus.splice(plus.length - 3, 3);
    let maxPlus = threePlus[threePlus.length - 1];
    let twoMinus = minus.splice(0, 2);
    let threeMinus = minus.splice(minus.length - 3, 3);

    threePlus.length === 3
      ? (subPlus = threePlus.reduce((a, b) => a * b))
      : (subPlus = threeMinus.reduce((a, b) => a * b));
    twoMinus.length > 1 && maxPlus
      ? (subMinus = twoMinus.reduce((a, b) => a * b) * maxPlus)
      : (subMinus = subPlus);

    return subPlus > subMinus ? subPlus : subMinus;
  }
};

 

더 깔끔하게 만드는 것을 포기하다가 구글링을 통해 깔끔한 로직과 깨끗한 코드를 발견했다. (출처 : 블로그) 직관적으로 누구나 코드를 봐도 로직이 이해가 되는 깔끔한 코드... 앞으로는 한 번 더 고민해봐야겠다...

 

function largestProductOfThree (array) {
  array.sort(function(a, b) {return a-b});
  var prod1 = array[array.length - 3] * array[array.length - 2] * array[array.length - 1];
  var prod2 = array[0] * array[1] * array[array.length - 1];
  return Math.max(prod1, prod2);
}