[Javascript] 수식 최대화 (67257)

문제링크

코딩테스트 연습 - 수식 최대화

 

접근 방법
1. `expression = "100-200*300-500+20"` 같이 문자열로 되어있는 식을 숫자 + 연산자 형태의 배열로 만들어야 한다. => 정규식 사용

const re = /[-*+]/g;
const operationArr = expression.match(re);
// [모든 연산자 출력]
const numArr = expression.split(re).map(e => parseInt(e));
// [모든 숫자 출력]​

2. 연산자의 우선순위의 순열을 구해야한다. (최대 연산자의 종류가 3개이므로 3!이 최대)

// 재귀를 이용하여 순열의 모든 경우의 수 도출
const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((el) => [fixed, ...el]);
    results.push(...attached); 
  });

  return results;
}​

 

순열과 조합을 잘 설명한 블로그

3. 우선순위를 이용하여 결과를 도출하는 함수를 만들어야 한다. 

1. 에서 구한 numArr과 operationArr을 출력해보면 (expression = "100-200*300-500+20" 인 경우)
연산자와 피연산자의 index 번호가 같은 것을 알 수 있다.

이를 이용하여 operationArr === "우선순위가 높은 연산자" 일때
numArr[index], numArr[index+1] 과 operationArr[index]를 연산하면 우선순위대로 결과를 출력할 수 있다.

그리고 splice()를 통해 연산이 끝난 element를 지워주면 원하는 값을 얻을 수 있다.

위 코드는 우선순위가 ("*", "+", "-") 인 경우를 임의로 정해서 구한 결과이다.


배운 부분

1. operationResult에서 operation을 문자인 oper1, oper2, oper3으로 받았는데,
이를 다시 numArr[i] oper1 numArr[i+1] 을 처리하기 위해 연산자로 치환하는 방법을 배웠다.
=> eval() 메서드를 사용하면 문자를 연산자로 사용할 수 있었다.

2. operationResult(numArr, operationArr, oper1, oper2, oper3)로 호출하면 원본 배열인 numArr, operationArr이 변해서 permutationOper의 값들을 모두 순환할때 원하는 값을 얻을 수 없었다.
=> spread 연산자를 통해 얕은 복사를 하여서 원본 배열에 영향을 주지 않도록 operationResult 함수를 호출하였다.

3. 처음 구현한 로직은 연산자가 3개 모두 존재할때를 기준으로 잡았다. 
하지만 연산자가 하나인 경우, 두개인 경우도 있어서 이를 처리하기 위해
oper2 !== undefined, oper3 !== undefined 조건을 추가하였다. 
또한 operationResult(oper1, oper2, oper3)을 operationResult( ...e)으로 호출 할 수 있다는 점도 배웠다.
(permutationOper.forEach(e => )에서 만약 e의 길이가 2라면 oper1, oper2, 길이가 1이라면 oper1만 호출하고 나머지는 undefined로 할당한다.)

 

 

function solution(expression) {
  var answer = [];
  const re = /[-*+]/g;
  const operationArr = expression.match(re);
  const numArr = expression.split(re).map(e => parseInt(e));
  
  let uniqueOper =  new Set(operationArr);
  uniqueOper = Array.from(uniqueOper);
  
  let permutationOper =  getPermutations(uniqueOper, uniqueOper.length)
  permutationOper.forEach(e => {
      answer.push(operationResult([...numArr], [...operationArr], ...e))
  })
  
  return Math.max(...answer);
}

const operationResult = (numArr, operationArr, oper1, oper2, oper3) =>{
let result = 0;
for(let i = 0; i <= operationArr.length; i++){
  if(operationArr[i] === oper1){
    result = eval(numArr[i] +  oper1 + numArr[i+1]);
    numArr.splice(i,2,result);
    operationArr.splice(i,1);
    i = -1;
    result = 0;
    continue;
  }else if(!operationArr.includes(oper1) && operationArr[i] === oper2 && oper2 !== undefined){
    result = eval(numArr[i] +  oper2 + numArr[i+1]);
    numArr.splice(i,2,result);
    operationArr.splice(i,1);
    i = -1;
    result = 0;
    continue;
  }else if(!operationArr.includes(oper2) && operationArr[i] === oper3 && oper3 !== undefined){
    result = eval(numArr[i] +  oper3 + numArr[i+1]);
    numArr.splice(i,2,result);
    operationArr.splice(i,1);
    i = -1;
    result = 0;
    continue;
  }
}
return Math.abs(numArr[0]);
}

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
    const permutations = getPermutations(rest, selectNumber - 1);
    const attached = permutations.map((el) => [fixed, ...el]);
    results.push(...attached); 
  });

  return results;
}