[DFS] 수식 최대화

[ericagong]

⭐ 성찰

1. 가능한 케이스가 많지 않은 경우라면 굳이 DFS 할 필요 없이 하드 코딩 하는 것도 괜찮음.
   • 코테에서 하드코딩도 하나의 풀이법이 될 수 있다는 점을 늘 인지하기!
2. 계산 시, stack.pop()을 이용하여, 마지막 계산 값에 접근 가능!

❓ 문제 상황

수식 최대화

👨‍💻 문제 해결: DFS를 통한 완전 탐색

✅ 1차 풀이: Stack을 통한 계산

1. 우선 순위 가능한 조합 모두 구하기 -> DFS를 통한 permutation 구현
2. DFS return 문 직전 조합에 대해 연산 수행해 최대값 반영

   
   function calc(num1, op, num2) {
   switch (op) {
   case "+":
     return num1 + num2;
   case "-":
     return num1 - num2;
   case "*":
     return num1 * num2;
   }
   }

const perms = []; let max_result = -Infinity; function dfs(cnt, arr, visited, exps) { if (cnt === arr.length) { perms.forEach((prior_op) => { const stack = [exps[0]]; for (let i = 1; i < exps.length - 1; i += 2) { const num1 = stack.pop(); const num2 = exps[i + 1]; const op = exps[i]; if (op === prior_op) { const result = calc(num1, op, num2); stack.push(result); } else { stack.push(num1); stack.push(op); stack.push(num2); } } exps = stack; }); const result = Math.abs(exps[0]); max_result = Math.max(result, max_result); return; }

for (let i = 0; i < arr.length; i++) { if (visited[i]) continue; perms.push(arr[i]); visited[i] = true; dfs(cnt + 1, arr, visited, exps); perms.pop(); visited[i] = false; } }

function solution(expression) { const regex = /[/+-/*]/g; const ops = expression.match(regex); const nums = expression.split(regex).map(Number); const exps = [nums[0]]; for (let i = 0; i < ops.length; i++) { exps.push(ops[i]); exps.push(nums[i + 1]); }

const op_arr = [...new Set(ops)]; const visited = new Array(op_arr.length).fill(false);

dfs(0, op_arr, visited, exps);

return max_result; }

### ✅ 2차 풀이: 하드 코딩으로 조합 대체
1. 우선 순위 가능한 조합 모두 구하기 -> 하드코딩
2. DFS return 문 직전 조합에 대해 연산 수행 시 `eval` 사용
```javascript
function solution(expression) {
  const splitted = expression.split(/([\*\+-])/g);

  const solve = (precedence, left = 0, right = splitted.length) => {
    if (left + 1 === right) {
      return eval(splitted[left]);
    }

    for (const operator of precedence) {
      for (let i = right - 2; i > left; i -= 2) {
        if (splitted[i] === operator) {
          return eval(
            `${solve(precedence, left, i)}${operator}${solve(
              precedence,
              i + 1,
              right
            )}`
          );
        }
      }
    }

    return Number.POSITIVE_INIFINITY;
  };

  return Math.max(
    ...[
      ["*", "+", "-"],
      ["*", "-", "+"],
      ["+", "*", "-"],
      ["+", "-", "*"],
      ["-", "*", "+"],
      ["-", "+", "*"],
    ]
      .map((precedence) => solve(precedence))
      .map(Math.abs)
  );
}