[boj] 2309. 좌표 압축 (node.js)

문제 요약

[boj] 2309. 일곱 난쟁이 (node.js)

• 조건에 맞도록 완전탐색을 수행한 후, 조건에 맞는 답을 정렬하여 출력

풀이

풀이 01: rec(k)

const solution = () => {
  let arr = [];
  for (let i = 0; i < 9; i++) arr[i] = Number(input());
  let sum = 0;
  let used = [];
  rec(0);

  function rec(k) {
    if (k >= 8 || sum > 100) return false;
    if (k == 7 && sum == 100) return true;
    for (let i = 0; i < 9; i++) {
      if (used[i]) continue;
      used[i] = arr[i];
      sum += arr[i];
      let temp = rec(k + 1);
      if (temp)
        process.exit(
          console.log(
            used
              .filter((elem) => elem)
              .sort((a, b) => a - b)
              .join("\n")
          )
        );
      used[i] = 0;
      sum -= arr[i];
    }
  }
};

• used 와 sum 배열은 둘 다 rec함수 외부에 선언하고, k (몇 번째 자리)만을 인자로 전달하는 경우
• -> sum, used 값이 매 재귀마다 바뀌므로, 반환된 이후에는 모두를 이전 단계(해당 스코프 초기 상태)로 돌려놓아주어야 한다.

풀이 02: rec(k, sum, used)

function solution() {
  let arr = [];
  for (let i = 0; i < 9; i++) arr[i] = Number(input());
  rec(0, 0, []);

  function rec(k, sum, used) {
    if (k >= 8 || sum > 100) return false;
    if (k == 7 && sum == 100) return true;
    for (let i = 0; i < 9; i++) {
      if (used[i]) continue;
      used[i] = arr[i];
      let temp = rec(k + 1, sum + arr[i], used);
      if (temp)
        process.exit(
          console.log(
            used
              .filter((elem) => elem)
              .sort((a, b) => a - b)
              .join("\n")
          )
        );
      used[i] = 0;
    }
  }
}

• k, sum, used 모두를 인자로 전달하는 경우
• sum 값은 갱신하지 않고 인자 내에서 더해줬으므로 해당 스코프로 돌아오면 그대로다. 따라서 비워줄 필요가 없다.
• used 배열은 내부 값을 대입해준 다음에 재귀 함수를 호출했으므로, 원래대로 돌려놓기 위해서는 다시 비워줘야 한다.

주절주절

• 요즘 브루트포스 문제 풀 때마다 다 풀고 나면 생각보다 쉬운데! 접근과 오류 개선이 너무 오래 걸려서, 개념 정리가 덜 된 것 같아 쉬운 문제부터 보충하고 있다.
• 오늘은 재귀 함수에서 인자를 전달해주는 방식에 대해 두 가지 방식으로 테스트해봤다. 결론적으로 인자를 안에 넣고, 밖에 넣고는 둘 다 구현 가능하나, 외부에 변수가 선언되어 있는 경우는 넣고 빼는 걸 확실히 해줘야 한다. 또한 배열을 매개변수로 사용하는 경우에도 넣었는데 실패한 경우 제거해줘야 한다!

전체 코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function solution() {
  let arr = [];
  for (let i = 0; i < 9; i++) arr[i] = Number(input());
  rec(0, 0, []);

  function rec(k, sum, used) {
    if (k >= 8 || sum > 100) return false;
    if (k == 7 && sum == 100) return true;
    for (let i = 0; i < 9; i++) {
      if (used[i]) continue;
      used[i] = arr[i];
      let temp = rec(k + 1, sum + arr[i], used);
      if (temp)
        process.exit(
          console.log(
            used
              .filter((elem) => elem)
              .sort((a, b) => a - b)
              .join("\n")
          )
        );
      used[i] = 0;
    }
  }
}

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
});