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

🙌문제설명

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

☑️나의 풀이

완전탐색 한 것 중, 최솟값과 최댓값을 판단해야 하므로 dfs 풀이. 모든 경우의 수를 탐색해야 한다!

입력 정제 시, 각 줄의 데이터를 한번에 map으로 숫자로 가져온다.

계산기는 배열 생성해서, [0],[1]... 로 호출한다! 순서는 덧셈, 뺄셈, 곱셈, 나눗셈

나눗셈에서 parseInt(a/b)로 작성했는데 36%에서 틀렸다가 계속 나왔다... 절망ㅜㅜㅜ 찾아보니 자바스크립트의 0, -0이 다르다는 특징에 예외처리를 안해주어서 그렇다고 한다.. 

 

처음 호출할때는 연산자 개수는 0개, 결과는 주어진 숫자들의 첫번째 값을 사용한다.

 

dfs 함수에서 만약에 현재까지 수행한 연산자의 개수가 `N-1` 개라면, 모든 연산자를 썼을때이니 max min 갱신

 

아니면, 이제 완전탐색하기!

operator 연산지 배열 for문으로 돌면서

현재 연산자 개수가 0이면 다음 for 문을 돈다.

0이 아니라면 연산자의 개수를 1개 감소시키고, (현재 해당 연산자를 사용하겠다는 의미!)

해당 연산자로 dfs 함수를 재귀적으로 호출한다. 이때 calculator 함수로 해당 연산자에 해당하는 수식을 호출해 연산한 값을 result에 전달하고 횟수count 도 증가한다.

 

그리고 현재 해당 연산자를 사용했으니, 다시 연산자의 개수를 1개 증가시켜 복구한다.

 

결과 출력시, 최댓값과 최솟값을 출력한다. 값이 없으면 0을 출력한다. -0의 예외처리!

 

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n").map((v) => v.split(" ").map(Number));

const [N, nums, operator] = input;

let max = Number.MIN_SAFE_INTEGER;
let min = Number.MAX_SAFE_INTEGER;

const calculator = [
  (a, b) => a + b,
  (a, b) => a - b,
  (a, b) => a * b,
  (a, b) => parseInt(a / b),
];

const dfs = (count, result) => {
  if (count === N - 1) {
    max = Math.max(max, result);
    min = Math.min(min, result);
  } else {
    for (let i = 0; i < operator.length; i++) {
      if (operator[i] === 0) {
        continue;
      }
      operator[i]--;
      dfs(count + 1, calculator[i](result, nums[count + 1]));
      operator[i]++;
    }
  }
};

dfs(0, nums[0]);

console.log(max ? max : 0);
console.log(min ? min : 0);

 

 

`Number.MAX_SAFE_INTEGER` : 자바스크립트에서 안전한 정수 표현의 최소값, 최대값을 나타낸다.

 

`(a, b) => parseInt(a / b)` 틀림

자바스크립트에서는 0, -0 을 다르다고 인식하기 때문에 나눗셈 연산에서 `비트연산자`로 작성하거나 예외처리를 해야한다.

 

 

dfs 함수 백트래킹 방식

연산자 갯수만큼 반복한다.

다음 수와 현재 결과를 계산해서 dfs 함수를 재귀로 호출하고,

이후에는 다음 경우를 탐색한다.

1. 현재까지의 계산 결과`result`와 사용 가능한 연산자를 인자로 받는다.
2. 현재까지의 연산자 사용 상태를 기억하기 위해 재귀 호출 전에 연산자 개수를 변경하고, 재귀 호출 후에 다시 복구한다.
3. 재귀 호출을 통해 모든 가능한 조합을 탐색한다.
4. 재귀 호출을 통해 모든 연산자를 사용하여 계산한 후, 결과를 최대값과 최소값과 비교하여 갱신한다.
5. 모든 재귀 호출이 종료되면, 최대값과 최소값을 찾았다.

 

☑️배운 점

`Number.MAX_SAFE_INTEGER`

Number.MAX_SAFE_INTEGER - JavaScript | MDN

 

자바스크립트 0, -0

 

재귀함수 백트래킹 순서! 백트래킹 재귀함수 호출이 DFS 구현의 포인트 인것 같다.

DFS 문제를 보면 우선 생각해야할 것 ! 어떤 조건으로 백트래킹을 돌아야 할지 ! 순서와 로직을 먼저 생각해보자

완전탐색에 대한 로직에 익숙해져야 할 필요가 있다. 비슷한 빈출되는 문제에서는 공식이 있을 것 같기도 하다.