일곱 난쟁이

문제

접근 및 풀이

9개중 7개를 택하는 9C7 조합(combination)으로 접근하는 방법밖에 떠오르지 않았는데 풀이를 보니 더 간단한 방법이 있었다. 9개 중 7개를 선택하는 대신 2개를 선택하는 방법을 택하는 것이다. 기존에 생각했던 대로 풀었더라면 7중 for문이나 깊은 콜스택의 재귀함수를 써야했다.

코드

/* 일곱 난장이 */

/* user code */
function answer(dwarf) {
  let result = [...dwarf];
  const fake = dwarf.reduce((acc,cur)=>{
    return acc + cur;
  }) - 100;
  for (let i = 0; i < dwarf.length; i++) {
    for (let j = i + 1; j < dwarf.length; j++) {
      if (dwarf[i] + dwarf[j] === fake) {
        const fakeDwarfValue1 = dwarf[i];
        const fakeDwarfValue2 = dwarf[j];
        result.splice(result.indexOf(fakeDwarfValue1),1);
        result.splice(result.indexOf(fakeDwarfValue2),1);
      }
    }
  }
  return result;
}

/* main code */
let input = [
  // TC: 1
  [1, 5, 6, 7, 10, 12, 19, 29, 33],

  // TC: 2
  [25, 23, 11, 2, 18, 3, 28, 6, 37],

  // TC: 3
  [3, 37, 5, 36, 6, 22, 19, 2, 28],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

출처

zero-base 연습 문제