문제 설명

백준 0 만들기 문제 풀이(https://www.acmicpc.net/problem/7490)

문제 개요

주어진 정수 N에 대해 1부터 N 까지의 숫자를 순서대로 나열하면서, 각 숫자 사이에 +, -, (공백) 연산자를 삽입해 수식을 만든다.
이때, 수식의 값이 0이 되는 경우만 출력하는 문제이다.

코드 구현

javascript

const input =
  process.platform === "linux"
    ? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
    : require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
 
N = parseInt(input[0]);
const answer = [];
 
const isSumIsZero = (currentNumberString) => {
  return eval(currentNumberString.replaceAll(" ", "")) === 0;
};
 
const makeNumberString = (operatorArr, lastNumber, arr) => {
  if (operatorArr.length === lastNumber - 1) {
    const strArr = [];
    for (let i = 1; i <= lastNumber; i++) {
      strArr.push(i);
      const operator = operatorArr.pop();
      if (operator) strArr.push(operator);
    }
    if (isSumIsZero(strArr.join(""))) arr.push(strArr.join(""));
    return;
  }
  makeNumberString([...operatorArr, "+"], lastNumber, arr);
  makeNumberString([...operatorArr, "-"], lastNumber, arr);
  makeNumberString([...operatorArr, " "], lastNumber, arr);
};
 
for (let i = 1; i <= N; i++) {
  const arr = [];
  makeNumberString([], parseInt(input[i]), arr);
  arr.sort();
  arr.forEach((el) => console.log(el));
  console.log();
}

코드 해설

이 문제는 완전 탐색(Brute Force) + 재귀함수를 활용해 해결할 수 있다.

재귀 호출을 통해 연산자 조합 생성
- 1부터 N 까지 숫자 사이에 들어갈 연산자는 +, -, 총 세 가지이다.
- 연산자 개수는 총 N−1개가 되며, N−1개의 연산자가 결정되면 재귀 함수를 종료하고 저장된 연산자를 계산한다.
수식 값이 0인지 판별
- 생성된 수식에서 공백을 제거해(replaceAll) 숫자를 붙여 만든 후, eval()을 이용해 값을 계산한다.
- 결과가 0이면 배열에 추가한다.
출력 정렬
- 문제에서 아스키 코드를 기반으로 정렬이 필요하므로, 저장한 배열 정렬하여 출력한다.
이슈 사항
- 정렬을 하지 않아 1차로 통과하지 못했다.
- 출력에 문제가 있다고 해서, console.log() 형태로 개행 추가했다. 나는 \n 으로 개행을 했는데 OS 별 차이 있는 듯 하다.

요약 및 참고사항

정렬! 정렬하고 출력해야 한다.
문제 난이도는 그리 어렵지 않은 듯 하다. N 범위가 더 크다면 좀 더 생각해 봐야 할 듯 하다.