[백준] 15658번 연산자 끼워넣기(2) - JavaScript(NodeJS)

문제

15658번: 연산자 끼워넣기 (2)

 

풀이

연산자 끼워넣기 << 이전 연산자 끼워넣기 포스팅
이전에 작성한 코드를 기반으로 풀이했다.

 

두 문제의 차이는

14888번 문제는 N-1개의 연산자가 주어지지만,
이 문제는 N-1개 이상의 연산자가 주어진다.

 

코드에 대한 기본적인 설명은 14888번 문제를 참고하면 될 듯 하다.

 

 

작성한 코드의 차이점을 보면

 

14888번

최대, 최솟값을 구하기 위해 dfs 함수 외부에 temp 배열을 선언했다.
그래서 모든 재귀에서 temp배열을 사용하기 위해 원소를 push, pop 해줬다.
그리고 재귀에서 피연산자 사이에 연산자가 모두 배치되었다면 최대, 최솟값을 위한 모든 계산이 이루어지도록 했다.

 

 

해당 문제

시간초과 이슈로 조금 변형을 줬다.

 

함수 외부에 temp 배열을 선언하지 않고, 함수의 인수인 temp를 통해 이전의 연산값을 받도록 했다.

함수 내에서 재귀적인 호출을 시행할 때, 현재 temp 변수에서 연산을 통해 newTemp를 매개변수로서 다음 재귀에 전달했다.
또한 연산자가 모두 배치되었다면, 이미 연산의 결과가 temp에 담겨있으므로 최소,최대만 판단하도록 했다.

 

코드

const sol = (input) => {
  const N = +input[0];
  const numbers = input[1].split(" ").map(Number);
  const operator = input[2].split(" ").map(Number);
  const operObj = {
    0: (oper1, oper2) => oper1 + oper2,
    1: (oper1, oper2) => oper1 - oper2,
    2: (oper1, oper2) => oper1 * oper2,
    3: (oper1, oper2) => {
      if (oper1 < 0) {
        return -Math.floor(-oper1 / oper2);
      }
      return Math.floor(oper1 / oper2);
    },
  };

  let min = Number.MAX_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;
  function dfs(L, temp) {
    if (L === N - 1) {
      min = Math.min(min, temp);
      max = Math.max(max, temp);
      return;
    }

    for (let i = 0; i < 4; i++) {
      if (!operator[i]) continue;
      operator[i] -= 1;
      const nextTemp = operObj[i](temp, numbers[L + 1]); // 재귀 호출 전에 미리 연산을 하고 결과를 다음 재귀로 전달한다.
      dfs(L + 1, nextTemp);
      operator[i] += 1;
    }
  }
  dfs(0, numbers[0]);

  return `${max}\n${min}`;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });