[프로그래머스] 카카오인턴 - 수식 최대화(js)

level2라길래 처음에는 어떻게든 풀겠지... 라고 생각했는데 구현하는 부분에서 오래걸렸다 ㅠ
블로그찬스 쓸까 유혹도 있었지만 다른사람 코드를 보면 그 사람의 코드에 기준이 생겨서 자연스럽게 내 생각을 못하는 결과를 여러번 맛봤기에 혼자서 풀어내려 노력했다.

문제는 문자열 속 연산자의 우선순위에 따라 연산을 하면 되는 문제이다. 주의할 점은

1. 연산자 두개가 같은 우선순위를 가질 수 없다.(무조건 A연산자가 B연산자보다 우선순위가 높다)
2. 우선순위가 같은 연산자가 두개 이상이면 맨 앞부터 연산한다.

연산자는 총 3개까지만 주어질 수 있다. 즉, 우선순위 조합은 최대 6개가 끝이다.
-, * 두개의 연산자가 주어지면 가능한 우선순위 조합은 -, *와 *, -이고,
-, *, + 세 개의 연산자가 주어지면, 아래와 같이 6개의 조합이 가능하다.

1. + - *
2. + * -
3. - + *
4. - * +
5. * + -
6. * - +

풀이 순서는

1. 우선순위 조합 배열을 구하고,
2. 이를 순회하면서 연산을 수행하고,
3. 절대값이 최대가 되는 값을 뽑아 반환한다.

📌 풀이 과정

우선순위 조합을 구하기 전에 먼저 주어진 문자열에서 정규표현식을 이용해 숫자부분, 연산자부분을 배열로 저장해줬다.
또, 우선순위 조합을 구하기위해 new Set()을 통해 연산자의 중복을 제거해준다.

const regexOfNumber = /[^\+|\*|\-][0-9]{0,3}/g; // 숫자만 뽑기위한 정규표현식
const regexOfOp = /\+|\-|\*/g; // 연산자만 뽑기위한 정규표현식(우선순위 분류를 위해) 
const arr = expression.match(regexOfNumber); // 숫자배열
const opArr = expression.match(regexOfOp) // 연산자배열

// 우선순위를 위한 변수(연산자 중복제거 배열, 배열 길이, 방문체크)
const opSet = [...new Set(expression.match(regexOfOp))];
const n = opSet.length;

순열로 우선순위 배열을 반환하는 함수를 생성한다.

const getPrior = (n, arr, newArr, visit, results) => {
  if (newArr.length === n) {
    results.push([...newArr]);
  }

  for (let i = 0; i < n; i++) {
    if (newArr.includes(arr[i])) continue;
    visit[i] = true;
    newArr.push(arr[i]);
    getPrior(n, arr, newArr, visit, results);
    newArr.pop();
    visit[i] = false;
  }
  return results;
};

함수를 통해 반환된 우선순위 배열을 변수에 저장하고, 우선순위에 따라 연산 시작 !

// 우선순위조합 배열
const prior = getPrior(n, opSet, [], visit, []);
let maxNumber = 0;
let answer = [];
>
// 연산시작
const prior = getPrior(n, opSet, [], visit, []);
let answer = [];
>
prior.forEach((v) => {
  let stack = [...arr];
  let opStack = [...opArr];
  for (const op of v) {
    // v는 우선순위에 따른 연산자 배열을 반복문으로 돌면서 연산 -> (배열이 우선순위에 따른 순서로 되어있기 때문에 순서대로 돌면 됨)
    if (op === "-") {
      // '-'연산자가 없어질때까지 계속 연산
      while (opStack.includes("-")) {
        for (let i = 0; i < stack.length; i++) {
          if (opStack[i] === op) {
            // 숫자 배열에서 연산자에 따른 연산 후 다시 삽입(i번째부터 2개를 뽑고, i번째에 연산한 값 삽입)
            stack.splice(i, 2, parseInt(stack[i]) - parseInt(stack[i + 1]));
            // 연산 후 연산자 배열에서 해당 연산자를 제거
            opStack.splice(i, 1);
            // 연산자가 같다면 맨 왼쪽이 우선순위가 크므로, 순차적으로 연산해야함! 그래서 한번 연산 후 break!
            break;
          }
        }
      }
    } else if (op === "+") {
      while (opStack.includes("+")) {
        for (let i = 0; i < stack.length; i++) {
          if (opStack[i] === op) {
            stack.splice(i, 2, parseInt(stack[i]) + parseInt(stack[i + 1]));
            opStack.splice(i, 1);
            break;
          }
        }
      }
    } else if (op === "*") {
      while (opStack.includes("*")) {
        for (let i = 0; i < stack.length; i++) {
          if (opStack[i] === op) {
            stack.splice(i, 2, parseInt(stack[i]) * parseInt(stack[i + 1]));
            opStack.splice(i, 1);
            break;
          }
        }
      }
    }
  }
  // 모든 연산이 끝난 후 값을 answer에 push
  answer.push(...stack);
});

answer에 저장된 숫자들 중 절대값이 가장 큰 값 반환

// 값들 중 절대값이 가장 큰 숫자를 반환
return Math.max(...answer.map((v) => Math.abs(v)));

📌 전체 코드

function solution(expression) {
  const regexOfNumber = /[^\+|\*|\-][0-9]{0,3}/g; // 숫자만 뽑기위한 정규표현식
  const regexOfOp = /\+|\-|\*/g; // 연산자만 뽑기위한 정규표현식(우선순위 분류를 위해)

  const arr = expression.match(regexOfNumber); // 숫자배열
  const opArr = expression.match(regexOfOp); // 연산자배열

  // 우선순위를 위한 변수(연산자 중복제거 배열, 배열 길이, 방문체크)
  const opSet = [...new Set(expression.match(regexOfOp))];
  const n = opSet.length;
  const visit = new Array(opSet.length).fill(false);

  // 우선순위 별로 뽑힌 연산자 배열
  const prior = getPrior(n, opSet, [], visit, []);
  let answer = [];

  prior.forEach((v) => {
    let stack = [...arr];
    let opStack = [...opArr];
    for (const op of v) {
      // v는 우선순위에 따른 연산자 배열을 반복문으로 돌면서 연산 -> (배열이 우선순위에 따른 순서로 되어있기 때문에 순서대로 돌면 됨)
      if (op === "-") {
        // '-'연산자가 없어질때까지 계속 연산
        while (opStack.includes("-")) {
          for (let i = 0; i < stack.length; i++) {
            if (opStack[i] === op) {
              // 숫자 배열에서 연산자에 따른 연산 후 다시 삽입(i번째부터 2개를 뽑고, i번째에 연산한 값 삽입)
              stack.splice(i, 2, parseInt(stack[i]) - parseInt(stack[i + 1]));
              // 연산 후 연산자 배열에서 해당 연산자를 제거
              opStack.splice(i, 1);
              // 연산자가 같다면 맨 왼쪽이 우선순위가 크므로, 순차적으로 연산해야함! 그래서 한번 연산 후 break!
              break;
            }
          }
        }
      } else if (op === "+") {
        while (opStack.includes("+")) {
          for (let i = 0; i < stack.length; i++) {
            if (opStack[i] === op) {
              stack.splice(i, 2, parseInt(stack[i]) + parseInt(stack[i + 1]));
              opStack.splice(i, 1);
              break;
            }
          }
        }
      } else if (op === "*") {
        while (opStack.includes("*")) {
          for (let i = 0; i < stack.length; i++) {
            if (opStack[i] === op) {
              stack.splice(i, 2, parseInt(stack[i]) * parseInt(stack[i + 1]));
              opStack.splice(i, 1);
              break;
            }
          }
        }
      }
    }
    // 모든 연산이 끝나면 stack에 마지막 연산값이 들어가있다.
    answer.push(...stack);
  });
  return Math.max(...answer.map((v) => Math.abs(v)));;
}

const getPrior = (n, arr, newArr, visit, results) => {
  if (newArr.length === n) {
    results.push([...newArr]);
  }

  for (let i = 0; i < n; i++) {
    if (newArr.includes(arr[i])) continue;
    visit[i] = true;
    newArr.push(arr[i]);
    getPrior(n, arr, newArr, visit, results);
    newArr.pop();
    visit[i] = false;
  }
  return results;
};