[백준] 16937번, 괄호 추가하기(JavaScript)

Algorithm

문제 정보 : 괄호 추가하기

• 문제 분류 : 알고리즘 연습 중급 2/3, 브루트 포스 문제 (연습)
• 문제 출처 : 백준 골드 4, 괄호 추가하기

시작하며 ✅

문제 자체는 이전에 유사한 문제를 풀어봐서 괄호를 사용할 연산자를 조합해서 풀어야 겠다는 생각이 바로 들었다. 하지만 괄호를 적용한 연산을 계산하는 것에서 상당히 애먹은 문제였다.

접근 과정

문제에서 중복되는 괄호가 없으며 괄호 안에는 오직 하나의 연산자만 들어갈 수 있기 때문에 괄호 사이의 거리가 최소 한 칸 이상 떨어지도록 조합을 구현했다.
이후 계산 과정에서는 스택을 이용하여 뒤에서부터 연산자와 숫자들을 하나씩 삽입하고 다시 스택에서 POP하면서 최종 결과를 연산했다.

풀이 과정 ✨

1. DFS로 조합을 구현한다.
   1-1 이때, 1번을 선택했으면 다음은 3번 부터 선택하도록 한다.
2. 계산식을 만드는 데 스택을 이용한다.
   2-1 연산자의 숫자를 거꾸로 세면서 괄호를 이용하는 경우와 그렇지 않은 경우를 구분하여 연산할 것들을 스택에 쌓는다.
   2-2 이후, 스택을 거꾸로 POP하면서 연산을 하면 수식을 앞에서부터 연산하는 것과 동일한 결과를 얻을 수 있다.
   2-3 계산된 결과값을 현재까지의 정답과 비교하여 더 큰 값을 정답으로 설정한다.

코드 (시간초과 풀이)

// const readFileSyncAddress = '/dev/stdin';
const readFileSyncAddress = "text.txt";

let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const opers = [];
const nums = [];
let answer = -Infinity;

input[1].split("").forEach((el) => {
  if (0 <= Number(el) && Number(el) <= 9) {
    nums.push(Number(el));
  } else {
    // [ 연산자, 괄효 여부]
    opers.push([el, false]);
  }
});

function dfs(cnt, start) {
  calc();

  for (let i = start; i < opers.length; i++) {
    if (i > 0 && opers[i - 1][1]) continue;

    opers[i][1] = true;
    dfs(cnt + 1, i + 1);
    opers[i][1] = false;
  }
}

function calc() {
  let numsCnt = nums.length - 1;
  let operCnt = opers.length - 1;

  const stack = [nums[numsCnt]];
  numsCnt--;

  while (operCnt >= 0) {
    const [oper, isSelected] = opers[operCnt];
    operCnt--;

    if (isSelected) {
      const post = stack.pop();
      const pre = nums[numsCnt--];
      const tmp = eval(`${pre} ${oper} ${post}`);

      stack.push(tmp);
    } else {
      stack.push(oper);
      stack.push(nums[numsCnt--]);
    }
  }

  let result = stack.pop();

  while (stack.length) {
    const oper = stack.pop();
    const post = stack.pop();

    result = eval(`${result} ${oper} ${post}`);
  }

  answer = Math.max(answer, result);
}

dfs(0, 0);

console.log(answer);

마치며 🚩

좀 더 쉽고 간단하게 풀 수 있는 방법이 있을 거 같은데.. 떠올리지 못해서 아쉽다. 다른 분들의 풀이를 좀 더 참고해야겠다.