[프로그래머스][JS]수식 최대화

문제

문제: https://programmers.co.kr/learn/courses/30/lessons/67257

"100-200*300-500+20"

위와 같은 문자열이 주어졌을 때, -,+,*의 우선순위를 임의로 정해 결과의 절댓값이 가장 높은 결과를 출력하는 문제

우선순위를 정하기 위해 순열도 사용해야 되고 그 순열을 반복함에 있어서 반복문이 3번이나 중첩됐다. 보다 효율적인 방법을 생각해봐야 할 것 같다.

해결방법

1. 주어진 문자열을 배열로 tokenize해준다.
   ex)"100+300*5" ->[100,'+',300,'*',5]
2. tokenize하면서 부호만 따로 배열에 저장해주고 중복을 제거한다.
   (signArr)
3. 부호에 우선순위를 정해주기 위해 순열로 모든 경우의 수를 저장해준다.
4. 순열로 구한 경우의 수를 이용해 tokenize한 배열로 각각의 결과값을 구한다.
5. 결과값 중 절대값이 가장 높은 값을 출력한다.

코드

function solution(expression) {
  const signFn = {
    //각 부호에 따른 함수
    '*': (num1, num2) => num1 * num2,
    '+': (num1, num2) => num1 + num2,
    '-': (num1, num2) => num1 - num2
  };
  let [arr, signArr] = tokenize(expression); //tokenize한 배열, 부호만 있는배열
  signArr = [...new Set(signArr)]; //부호 중복제거
  signArr = permutation(signArr, signArr.length); //부호의 모든 경우의수를 순열로 구함.
  let totNum = []; //각 경우의 계산결과의 합

  for (let sign of signArr) {
    const tmpArr = [...arr];
    for (let nowSign of sign) {
      for (let i = 0; i < tmpArr.length; i++) {
        if (tmpArr[i] === nowSign) {
          const calculated = signFn[tmpArr[i]](tmpArr[i - 1], tmpArr[i + 1]);
          tmpArr[i - 1] = calculated;
          tmpArr.splice(i, 2);
          i = i - 1;
        }
      }
    }
    totNum.push(tmpArr[0]);
  }
  totNum = totNum.map((v) => Math.abs(v));
  return Math.max.apply(null, totNum);
}
function tokenize(str) {
  let arr = [];
  let signArr = [];
  let start = 0;
  for (let i = 0; i < str.length; i++) {
    if (isNaN(parseInt(str[i]))) {
      arr.push(str.slice(start, i) * 1);
      arr.push(str[i]);
      signArr.push(str[i]);
      start = i + 1;
    }
  }
  arr.push(str.slice(start) * 1);
  return [arr, signArr];
}
function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuteArr = permutation(restArr, selectNum - 1);
    const combine = permuteArr.map((v) => [fixer, ...v]);
    result.push(...combine);
  });
  return result;
}