백준14888 - 연산자 끼워넣기 (백트래킹, Math.floor & parseInt 차이) node.js

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

해당 문제에서는 연산을 통해 최댓값, 최솟값을 만들 수와 연산자의 갯수가 각각 주어지고, 해당 요소들을 통해 만들 수 있는 최댓값, 최솟값을 출력하면 된다.

 

문제 풀이 방식

최대, 최솟값을 구하기 위해 백트래킹 알고리즘으로 접근했다. 

연산의 사용할 수를 numbers 배열, 연산자들의 갯수를 opts로 초기화한 뒤, 백트래킹 로직을 작성했다.

백트래킹 함수는 현재값, 깊이, 연산자들의 갯수를 인자로 하며, 해당 '깊이'가 글자수와 같을 때 (즉 모든 연산을 완료했을 때) 결괏값에 저장토록 했다.

함수 내부에서는 각 연산자마다 if문을 활용하여 각각의 로직을 작성할 수 있었지만, 개인적으로 좋아하지 않는 방식이기 때문에, 각 연산자마다의 수식을 table 객체에 저장하여 if문의 사용을 줄였다.

 

초기 작성 전체 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const N = +data.shift();
  const [numbers, opts] = data.map((el) => el.split(" ").map(Number));

  const table = {
    0: (a, b) => a + b,
    1: (a, b) => a - b,
    2: (a, b) => a * b,
    3: (a, b) => Math.floor(a / b),
  };

  let max = -Infinity,
    min = +Infinity;

  function DFS(cnt, depth, opts) {
    if (depth === N) {
      max = Math.max(max, cnt);
      min = Math.min(min, cnt);
      return;
    }

    opts.forEach((op, idx) => {
      if (op) {
        const total = table[idx](cnt, numbers[depth]);
        const newOpts = [...opts];
        newOpts[idx]--;
        DFS(total, depth + 1, newOpts);
      }
    });
  }

  DFS(numbers[0], 1, opts);

  console.log(max);
  console.log(min);
}

solution(input);

----

하지만 해당 코드에서 연산자에 '나누기'의 갯수가 1 이상 일 경우, 최댓값이 맞으면 최솟값이 틀린다거나 반대로 최솟값이 맞으면 최댓값이 틀리는 문제가 발생했다.

그리고 이는 Math.floor의 처리 방식 때문에 생기는 문제였는데, Math.floor의 경우 소숫점을 제외한 더 낮은 정수를 산출하는 내장 함수이기 때문에, 부호만 다른 실수를 대입한 경우 서로 다른 값이 나오게 된다. 

const a = Math.floor(12.34) // 12
const b = Math.floor(-12.34) // -13

하지만, 문제에서 원하는 나누기는 양수의 몫을 음수로 바꾸기이기 때문에 다른 방식을 사용해야 했다.

 

그리고 이 문제를 해결하기 위해 사용한 함수는 parseInt.

const a = parseInt(12.34) // 12
const b = parseInt(-12.34) // -12

parseInt 함수는 소숫점 자체를 버리기 때문에 해당 함수를 활용하여 문제 풀이가 가능했다.

Math.floor 와 parseInt 가 동일하게 동작한다고 생각했는데, 처음 알게된 사실이었다.

 

----

수정한 후 제출했으나 또 실패.

백준 질문 게시판에서 살펴본 결과, 나와 같은 문제를 겪은 사람을 발견할 수 있었는데, 자바스크립트의 number는 실수형이기 때문에 +0과 -0이 다른 값으로 인식된다고 한다.

따라서, 값이 0이더라도, 내 연산을 통해 나온 결과가 -0이라면 틀린 값이라는 것...;

이 부분은 사실 문제 출제자가 고려하지 못한 부분이라 이 부분을 예외처리하여 정답을 반환케했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const N = +data.shift();
  const [numbers, opts] = data.map((el) => el.split(" ").map(Number));
  const result = [];

  const table = {
    0: (a, b) => a + b,
    1: (a, b) => a - b,
    2: (a, b) => a * b,
    3: (a, b) => parseInt(a / b),
  };

  function DFS(cnt, depth, opts) {
    if (depth === N) {
      result.push(cnt);
      return;
    }

    opts.forEach((op, idx) => {
      if (op) {
        const total = table[idx](cnt, numbers[depth]);
        const newOpts = [...opts];
        newOpts[idx]--;
        DFS(total, depth + 1, newOpts);
      }
    });
  }

  DFS(numbers[0], 1, opts);

  const max = Math.max(...result) === 0 ? 0 : Math.max(...result);
  const min = Math.min(...result) === 0 ? 0 : Math.min(...result);

  console.log(max);
  console.log(min);
}

solution(input);