Programmers / Level 2 / 수식 최대화 / JS

< 문제 바로가기 >

프로그래머스

 

function getOperatorPermutationList(OP_LIST, num) {
  let result = [];

  if (num === 1) return OP_LIST.map((el) => [el]);

  OP_LIST.forEach((fixed, idx) => {
    let rest = [...OP_LIST.slice(0, idx), ...OP_LIST.slice(idx + 1)];
    let permutationList = getOperatorPermutationList(rest, num - 1);
    let attached = permutationList.map((el) => [fixed, ...el]);

    result.push(...attached);
  });

  return result;
}

function solution(expression) {
  let result = [];
  const OP_LIST = ['+', '-', '*'];

  const OP_PERMUTATION_LIST = getOperatorPermutationList(OP_LIST, 3);

  let seperatedExpression = '';
  OP_PERMUTATION_LIST.forEach((OP_PERMUTATION) => {
    seperatedExpression = expression.split(/(\D)/);
    
    OP_PERMUTATION.forEach((OP) => {
      while (true) {
        if (seperatedExpression.includes(OP) === false) break;

        let idx = seperatedExpression.indexOf(OP);
        let calcResult = eval(
          seperatedExpression.slice(idx - 1, idx + 1 + 1).join('')
        );
        seperatedExpression.splice(idx - 1, 3, calcResult);
      }
    });
    result.push(Math.abs(...seperatedExpression));
  });

  return Math.max(...result);
}

const expression = '100-200*300-500+20';
const result = solution(expression);
console.log(result);

---

연산자들의 모든 순열을 구하기 위해 순열 알고리즘을 사용했지만, 사실 3개만 사용하므로 직접 6개의 경우의 수를 배열에 초기화 시켜놓고 사용하는게 더 빠르다.(라는걸 다풀고나서야 깨달았다....)

 

들어온 expression 의 숫자와 연산자를 나누기 위해서 split() 메서드를 사용하였는데, /(\D)/ 정규표현식을 넣어주었다. 일단 정규표현식에서 \D는 숫자가 아닌 모든 문자를 의미한다. 따라서 /\D/를 하게 되면 숫자가 아닌 문자로 split()을 수행하겠다는 의미이다.

 

위의 코드에선 expression으로 '100-200*300-500+20'을 넣어주었는데, 문자로 split()을 수행하게 되면 [100, 200, 300, 500, 20]이 된다.

 

하지만 괄호를 넣어주어 그룹 캡쳐를 이용해 split()을 하게되면, 해당 그룹에 해당하는 문자까지 split()한 결과에 붙여서 나오게 된다. 따라서, \D에 해당하는 문자들과 그 문자들로 split()을 수행해서 얻은 숫자들을 얻는다. 즉, 연산자와 숫자를 구분하게 되는 효과를 얻을 수 있다.

 

그리고 난 후, 연산자의 우선순위를 정한 모든 경우의 수들을 순회하면서 연산자가 나왔을 경우에 해당 연산자로 앞, 뒤 연산자를 계산해서 그 식을 splice()로 대체해준다. 예를 들어 위에서 '100-200'을 계산한 값인 -100으로 대체해주는것이다. 이러한 과정을 현재 순회하고 있는 순열의 연산자 우선순위에 따라서 연산자가 없을 때까지 계속 해주면된다.

 

그리고 나서 끝까지 계산한 값을 절댓값을 취해 배열에 넣어준 후에 모든 순회가 끝나고 배열에 담긴 값 들 중에서 max 값을 구해서 반환해주면된다.