알고리즘_일곱 난쟁이 문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시 오.

입력설명
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
▣ 출력설명
입력된 순서대로 일곱 난쟁이의 키를 출력한다.
▣ 입력예제 1
20 7 23 19 10 15 25 8 13
▣ 출력예제 1
20 7 23 19 10 8 13

문제 못품, 비슷하게 생각했는데 중간에 막혀버렸다. 내가 만든 오답:

let input = [20, 7, 23, 19, 10, 15, 8, 13];

function solution(arr) {
  let subSum = 0,
    sum = 0,
    diff = 0;
  let otherThanAnswrArr = [];

  for (let element of arr) {
    sum += element;
    diff = sum - 100;
  }

  console.log(diff);

  let min = 100;
  for (let element of arr) {
    subSum += element;
    otherThanAnswrArr.push(element);
    if (subSum > diff) {
      for (let i = 0; i < otherThanAnswrArr.length; i++) {
        if (min > otherThanAnswrArr[i]) {
          min = otherThanAnswrArr[i];
        }
      }
      subSum -= min;
      otherThanAnswrArr = otherThanAnswrArr.filter((value) => value != min);
    }
    if (subSum === diff) {
      break;
    }
  }
  let flag = false;

  let answer = arr.filter((value) => {
    for (let i = 0; i < otherThanAnswrArr.length; i++) {
      if (value === otherThanAnswrArr[i]) {
      } else {
        flag = true;
      }
    }
    if (flag) {
      return value;
    }
  });

  return answer;
}

console.log(solution(input));

해설 : 일단 총 sum 하는 것 까지는 답안과 같았다. 그리고 -100 을 한 값과 난쟁이 두명을 더한 값과 같다면, 그 두명의 난쟁이를 잡아내어 삭제?제거? 하면 7명이 남게 되는 로직도 답안과 거의 비슷하다. 로직은 알겠는데 코드상으로 구현하는 과정에서 나는 '어떻게 임의의 2명을 각각 다 더할수 있지?' 라는 생각을 했다. 즉 임의의 2명을 더하는 방법을 생각 못했다. 자꾸 random() 같은 함수를 써서 난수를 뽑아서 인덱스로 하고 더할까? 이런 생각을 하다보니 소스가 산으로 가버린거다.
답은 알고보니 참 쉽다. 이중 for문을 사용해서 바깥 for문 index의 i를 설정하고, 내부 second for문 index를 j로 두면 j = i+1로 두고 마지막까지 돌리는 중단점? 이라 하나 그것만 주의하고 돌리면 2개의 요소를 모든 경우의 수로 더할수 있었다.

이중 for문 사용해서 i, j+1 방식을 잠깐 생각했었는데 난 단순하게 그러면 i=0이면 j=1 그리고 i=1이면 j=2 이런식으로 돌겠지라고 착각하고 내부 for문이 돌아가는 원리를 이상하게 간주해버린것이다. row col 데이터 처리할때 이중for문을 실무서 많이 사용해놓고 왜 알고리즘에서 이상하게 생각해버렸는지 모르겠다 ㅡ_ㅡ 경험 부족인것 같다.

최종 정답은

function solution(arr) {
  let answer = arr;
  //sum 구하는 방식
  let sum = answer.reduce((acc, b) => {
    // console.log(` acc : ${acc}, b : ${b}`); //reduce 함수 확인
    return acc + b;
  });
  // console.log(`sum : ${sum}`); //140

  for (let i = 0; i < answer.length - 1; i++) {
    for (let j = i + 1; j < answer.length; j++) {
      console.log(`when i === ${i}, then j === ${j}`);

      if (sum - (answer[i] + answer[j]) === 100) {
        // console.log(`answer[i] : ${answer[i]}, answer[j] : ${answer[j]}`);
        answer.splice(i, 1);
        answer.splice(j - 1, 1);

        console.log(`answer : ${answer}, and i : ${i} j: ${j}`);
      }
    }
  }
  console.log(`test : ${answer.reduce((acc, b) => acc + b)}`);
  return answer;
}

let arr = [15, 20, 7, 23, 19, 10, 8, 13, 25];
console.log(solution(arr));

결국 2개 요소 더해서 최종 sum값과의 차가 100과 같다면 그 요소의 인덱스를 삭제해서 출력하면, 7명의 난쟁이 정답이 나온다.
2개 요소 더하는 방식을 2중 for 문 쓰는걸 못 떠올려서 못풀었다. 실무서 많이 써도 알고리즘에선 왜케 생소하게 보이냐.. 숙련이 안됬고 이해가 약간 부족해서였을 것이다. 아니 많이 안써서 그렇겠지 뭐. 2중 for문도 거의 6개월에 한, 두번 사용할까 말까인데..
알고리즘 열심히 하자. 6개월만 꾸준히 해도 코드 읽는 속도나 짜는 레벨이 달라질것 같은 기대가 든다.