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

문제

14888번: 연산자 끼워넣기

 

풀이

문제가 길고 복잡해보이지만, 결론은 숫자 사이에 연산자를 끼워 넣은 모든 경우의 수를 조회하면 된다.
연산자의 연산은 앞에서부터 진행됨을 유의하면서 모든 연산을 진행하고, 최댓값과 최솟값을 구한다.

 

풀이 방향

 

연산자의 갯수가 주어지고, 이를 배열에 순차적으로 담는다.

0:+, 1:-, 2:*, 3:/ 에 대응하는 배열 인덱스를 활용해서 문제를 풀어본다.

 

수의 개수가 2<=N<=11 이므로 브루트 포스로 풀기에 충분하다.

 

연산자가 배치되는 모든 경우의 수를 조회할 것이며
연산자의 순서가 모두 배치된 시점에서 연산을 해서 최대 최솟값을 구해보자.

 

※ 주의사항

나눗셈을 할 때,

(음수 / 양수) 라면, (양수 / 양수) 로 바꿔주고, 몫을 취한 뒤 결과 값을 음수로 출력한다.

 

코드

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);
    }, // operObj 객체에 순차적으로 덧셈, 뺄셈, 곱셈, 나눗셈을 선언해둔다.
  };

  const temp = [];
  let min = Number.MAX_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;
  function dfs(L) {
    if (L === N - 1) { // 연산자는 숫자의 개수보다 1개 적으므로, 누적된 연산자가 N-1개라면 최대 최소값을 판단 할 것.
      let oper1 = numbers[0];
      for (let i = 0; i < temp.length; i++) {
        let oper2 = numbers[i + 1];
        let idx = temp[i];
        oper1 = operObj[idx](oper1, oper2); // operObj 객체를 이용해서 연산자에 따른 연산을 순차적으로 수행
      }
      if (oper1 > max) max = oper1;
      if (oper1 < min) min = oper1;
    }

    for (let i = 0; i < 4; i++) {
      if (!operator[i]) continue;
      operator[i] -= 1;
      temp.push(i);
      dfs(L + 1);
      operator[i] += 1;
      temp.pop();
    } // 모든 경우의 수를 따져야 하므로 재귀가 끝나면 연산자 배열과 임시 배열을 원래대로 되돌려야 한다.
  }
  dfs(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();
  });