삼각형 만들기

 

 

주의점

push는 원래배열을 변경하기 때문에 push, pop하기전에 

원래의 배열을 복사 해서 새로운 배열을 만든 뒤 ([...배열]  혹은 Array.from(배열)) 

push해서 변경한다

// push하기 전에 원래 값 저장
const beforePush = Array.from(curr); 
curr.push(selected);
dfs(newRemained, curr);
// 돌아온 뒤 원래값으로 돌아오기
curr = beforePush; // curr.pop(); !!!!

 

배열에서 한 값외의 배열을 선택하는 방법

1. filter: 새로운 배열을 반환한다.

배열.filter((e) => e !== selected);

 

2. splice

a는 원래 배열을 변경하고, 자르고 남은걸 반환하니까

a를 복사한 b를 만들고 b.splice(인덱스, 1)

const a = [1, 2, 3];
const b = [...a];
console.log(b.splice(1, 1)); // [2]
console.log(a, b); // [ 1, 2, 3 ] [ 1, 3 ]

 

삼각형이 되는 로직

두변의 길이합 > 최대 길이의 변 이면 삼각형이다.

 

function isValidFunc(arr) {
  const max = Math.max(...arr);
  const others = arr
    .filter((e) => e !== max)
    .reduce((acc, curr) => acc + curr, 0);
  return others > max ? others + max : false;
}

function solution(arr) {
  const answer = [];
  function dfs(curr, remained) {
    if (curr.length === 3) {
      // check is it valid triangle?
      const isValid = isValidFunc(curr);
      if (isValid) {
        answer.push(isValid);
      }
      return;
    }

    for (let i = 0; i < remained.length; i++) {
      const selected = remained[i];
      const newCurr = [...curr];
      newCurr.push(selected);
      const newRemained = remained.filter((e) => e !== selected);
      dfs(newCurr, newRemained);
    }
  }

  dfs([], arr);
  return answer.sort((a, b) => b - a)[0];
}

console.log(solution([6, 2, 12, 8, 5, 9]));