알고리즘(괄호 넣기)

알고리즘(괄호넣기)

최근 코딩테스트를 하던 중 못 풀었던 문제를 재구성했다
주어진 수식을 가지고 괄호를 1회 넣어서 구할수 있는 가장 높은 수를 구하라
ex) 1-2+3+4x5-6 => 28

function solution(str) {
  let answer = 0;
  const newStr = str.replace(/x/, "*");
  const numbers = newStr.split("");
  const requsive = (nums, index) => {
    const num = evalExpression(nums.join(""));
    answer = Math.max(answer, num);
    if (nums.length <= index) {
      return;
    }
    const newExpression = nums.concat();
    newExpression.splice(index, 1);
    newExpression.splice(index + 2, 0, ")");
    requsive(newExpression, index + 2);
  };
  for (let i = 0; i < numbers.length - 1; i += 2) {
    const newExpression = numbers.concat();
    newExpression.splice(i, 0, "(");
    newExpression.splice(i + 4, 0, ")");
    requsive(newExpression, i + 4);
  }

  return answer;
}

const evalExpression = (expr) => {
  try {
    return new Function(`return ${expr}`)();
  } catch (error) {
    return undefined;
  }
};

console.log(solution("1-2+3+4x5-6")); // 28

후기

evalExpression 이 함수를 몰라서 한참을 헤매었다. 자바스크립트 문자열을 받으면 함수로 변화해주는 함수이다. 예를 들어 "2 + 2" 문자열을 받으면 return 2 + 2;로 처리되어 결과값을 얻을수 있다.
동작과정을 for문을 통해 괄호의 시작점을 잡고 requsive를 통해 끝점을 만들면서 계산한 값 중 가장 큰 값을 저장합니다.

테스트케이스가 별로 없다보니 정확한 정답이 아닐지도 모른다. 다시한번 기회가 온다면 꼭 풀고 싶어지는 문제이다.