백준 7490번 0 만들기 JavaScript 풀이 [백트래킹]

백준 7490번 0 만들기 문제를 자바스크립트로 백트래킹 알고리즘을 이용해서 풀어보았다. 

https://www.acmicpc.net/problem/7490

 

처음 작성한 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 테스트케이스 개수
let testCase = Number(input[0]);
// 출력할 결과
let answer = "";

function backtrack (n, depth, result, operators, numbers) {
  if (depth == n-1) {
	  // 공백을 제거한 식
    let calculate = "";
    for (let r=0; r<result.length; r++) {
      if (result[r] != " ") calculate += result[r];
    }
    // 0이 되면 공백을 살려서 answer에 할당
    if (eval(calculate) == 0) answer += result.join("") + '\n';
    return;
  }

  // Operators([" ", "+", "-"] 순회)
  for (let i=0; i<3; i++) {
    result.push(operators[i]);
    if (depth != n-1) result.push(numbers[depth+1]);
    backtrack(n, depth + 1, result, operators, numbers);
    result.pop();
    result.pop();
  }
}

// 테스트케이스 순회
for (let t=1; t<=testCase; t++) {
  // 1부터 n까지 들어있는 배열
  let n = Number(input[t]);
  let numbers = Array.from({ length: n }, (v, i) => i + 1)
  
  // ASCII 순서에 따라 연산자 배치 
  // (charCodeAt으로 확인하면 32, 43, 45)
  let operators = [" ", "+", "-"]
  let result = [numbers[0]];
  
  backtrack(n, 0, result, operators, numbers);
  answer += '\n';
}
console.log(answer)

 

위의 코드도 통과했지만, 조금 더 수정한 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 테스트케이스 개수
let testCase = Number(input[0]);
// 출력할 결과
let answer = "";

function backtrack (n, depth, result, numbers) {
  if (depth == n-1) {
    // 0이 되면 answer에 할당
    let calculate = result.join("");
    if (eval(calculate.replaceAll(" ", "")) == 0) answer += calculate + '\n';
    return;
  }

  for (let op of [" ", "+", "-"]) { 
    result.push(op);
    if (depth != n-1) result.push(numbers[depth+1]);
    backtrack(n, depth + 1, result, numbers);
    result.pop();
    result.pop();
  }
}

// 테스트케이스 순회
for (let t=1; t<=testCase; t++) {
  // 1부터 n까지 들어있는 배열
  let n = Number(input[t]);
  let numbers = Array.from({ length: n }, (v, i) => i + 1)
  let result = [numbers[0]];
  backtrack(n, 0, result, numbers);
  answer += '\n';
}
console.log(answer)

 

replace는 첫 번째 찾은 문자열만 치환한다.
여러 개를 모두 치환하고 싶은 경우에는 replaceAll을 사용해야 한다.
공백을 없애고 싶을 때는 먼저 공백으로 split하고 join해도 된다. => str.split(' ').join('')