1회차:일곱 난쟁이

문제 탐색하기 (2039번:일곱난쟁이)

• 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
• 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
• 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성

입력

• 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다.
• 주어지는 키는 100을 넘지 않는 자연수.
• 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력.

출력

• 일곱 난쟁이의 키를 오름차순으로 출력한다.
• 일곱 난쟁이를 찾을 수 없는 경우는 없다.

---

접근 방법

1. 브루트포스로 푸는 방법으로 보였으나, 다른 방법이 있는지 고민해봤다.
2. 일곱 난쟁이가 누군지 모르지만 그들의 키의 합은 100이다.
3. 고정값이 있으니 반대로 생각해보면 9명의 난쟁이 수에서 100을 빼게 되면,
   초과되는 값의 경우의 수가 되는 두 난쟁이가 거짓 난쟁이 일 것이다. (두 수의 합)
   _e.g) 9명의 난쟁이의 키의 합 120이라면, 초과되는 키의 cm는 20. 두 명의 키의 합이 20의 경우의 수가 되는 경우를 찾으면 된다.
4. set을 이용하여 탐색을 𝑂(1)로 수행하므로 시간 복잡도는 𝑂(n)이 될 것이다.

풀이과정

1. 입력값을 배열로 만들어 모두 다 더한다 (메서드 reduce)
2. 접근 방법의 3번에 해당되는 과정을 거친다(변수 findRestNumber)
3. 진짜 난쟁이들을 담을 배열 (변수 arr)
4. 배열을 순회하면서 num을 선택하고, condition 값이 있는 지 확인한다.
5. 있다면 두 숫자를 찾은 것이므로 배열에서 제외한다.

const fs = require('fs');
const inputArray = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(Number);

const total = inputArray.reduce((sum, acc) => sum + acc, 0);
let findRestNumber = total - 100;
let seen = new Set();
let arr;

for (let num of inputArray) {
  let condition = findRestNumber - num;
  if (seen.has(condition)) {
    arr = inputArray.filter((item) => item !== num && item !== condition);
    break;
  }
  seen.add(num);
}

arr.sort((a, b) => a - b);

주의해야할 점 (혹은 더 공부하면 좋을 점)

1. sort의 특성을 모르고, sort()만 써서 작은 수대로 정렬될 줄 알고, 최대한 시간 줄여 보겠다고 reverse()를 썼다. 뒤집으면 큰 수대로 정렬될 줄 알았는데, 찾아보니 잘못된 생각이었다. 참고한 문서
2. set에 대한 시간 복잡도 이해도가 낮아서 고민이 되었다. 이 부분은 내가 생각한게 맞는지 챗지티피에게 물어봤다. 참고한 문서