[JavaScript] 백준 14888. 연산자 끼워넣기

문제 설명

입력 예시

- 2개의 숫자 5, 6이 주어짐

- 연산자 순서대로 +, -, x, ÷ 이 개수를 나타내며, 곱셈을 한개 가지고 있음을 의미

2
5 6
0 0 1 0

 

숫자 사이의 연산자를 원하는 대로 조합하여 구할 수 있는 결과값 중 가장 큰 값과 가장 작은 값을 리턴하는 문제이다.

 

문제 풀이

N <= 11이고, 사칙연산은 4종류이므로 아무리 많아봤자 4^11을 넘지 못한다.

이는 1초에 해당하는 1억번의 연산보다 적은 수이므로 모든 조합을 구한다, 즉 백트래킹 문제이다.

 

우선 사칙 연산의 결과를 리턴하는 함수를 별도로 분리했다.

function getResult(a, b, opNum) {
  if (opNum === 0) return a + b;
  else if (opNum === 1) return a - b;
  else if (opNum === 2) return a * b;
  else {
    return parseInt(a / b);
  }
}

 

백트래킹 함수를 구현했다.

백트래킹 함수에서 가장 중요한 것은 종료 조건, 그리고 for 반복문이다.

1) 종료 조건 : N이 되는 경우, 최대 최소 결과값을 업데이트

2) for 반복문 : 4칙연산에 대하여, 하나를 선택 후 이 연산자가 남아있다면 다음 함수 진행

function bt(idx, result) {
  if (idx === N) {
    minResult = Math.min(minResult, result);
    maxResult = Math.max(maxResult, result);
    return;
  }

  for (let opNum = 0; opNum < 4; opNum++) {
    if (op[opNum]) {
      op[opNum]--;
      bt(idx + 1, getResult(result, numbers[idx], opNum));
      op[opNum]++;
    }
  }
}

 

전체 코드

코드를 보여주기 전에, 짚고 넘어갈 게 있다.

자바스크립트는 +0과 -0을 구분한다. 
예를 들어, 0 * -1 = 0이 아닌 -0이다.

 

따라서 getResult() 함수의 리턴값으로 -0이 나올 수 있으며 그 결과 maxResult, minResult가 -0이 될 수 있다.

이를 보완하기 위해 maxResult ? maxResult : 0 코드를 작성했다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const N = Number(input[0]);
const numbers = input[1].split(" ").map(Number);
let op = input[2].split(" ").map(Number);

let minResult = Infinity;
let maxResult = -Infinity;
bt(1, numbers[0]);
console.log(maxResult ? maxResult : 0);
console.log(minResult ? minResult : 0);

function bt(idx, result) {
  if (idx === N) {
    minResult = Math.min(minResult, result);
    maxResult = Math.max(maxResult, result);
    return;
  }

  for (let opNum = 0; opNum < 4; opNum++) {
    if (op[opNum]) {
      op[opNum]--;
      bt(idx + 1, getResult(result, numbers[idx], opNum));
      op[opNum]++;
    }
  }
}

function getResult(a, b, opNum) {
  if (opNum === 0) return a + b;
  else if (opNum === 1) return a - b;
  else if (opNum === 2) return a * b;
  else {
    return parseInt(a / b);
  }
}