[프로그래머스 lev2/JS] 수식 최대화

문제 출처

프로그래머스 lev2 - 수식 최대화

나의 풀이 (통과)

풀긴 풀었지만 난해하게 푼 것 같다..

// 1. getPermutations 함수로 3!를 구했다. 경우의 수가 중요한 건 아니라서 그냥 배열로 손수 넣는 게 빨랐을지도 모르겠다.

// 2. 문자열로 된 계산식을 숫자와 연산자로 분류한 뒤 배열에 저장했다. 여기서 배열을 낭비해서 혹시 시간초과가 나지 않을까 걱정했는데 다행이다.
=> 다른 풀이에선 정규표현식 한 줄로 끝낼 수 있었다.
const splitted = expression.split(/([\*\+-])/g);

// 3. 이중 map을 순회하면서 첫번째 v에 대해 tmp를 생성한 뒤, 두번째 el로 tmp for문을 순회한다. 그럼 el가 각 cases의 순서대로 순회할 테니까 이 지점에서 우선순위에 따른 연산을 구현할 수 있다.

• 연산자가 한번에 여러 개 일 수 있으므로 if문이 아니라 while문으로 판단해줘야 누락이 없다.
• 문자열 연산은 op 함수로 구현했다.

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

  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((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });

  return results;
};

const op = function (a, b, ep) {
  a = a*1; b = b*1;
  if(ep === '-') return a-b;
  else if(ep === '+') return a+b;
  else if(ep === '*') return a*b;
}

function solution(expression) {
  let answer = 0;
  // 1. 
  const exp = ['*', '-', '+'];
  const cases = getPermutations(exp, 3);

  // 2. 
  let cal = [];
  let rexp = [];
  for(let i=0; i<expression.length; i++) {
    if(isNaN(expression[i])) {
      rexp.push(expression[i]);
      expression=expression.replace(expression[i], ' ');
    }
  }
  cal = [...expression.split(' ')];

  let j = 1;
  for(let i=0; i<rexp.length; i++) {
    cal.splice(j, 0, rexp[i]);
    j += 2;
  }

  // 3. 
  cases.map(v => {
    let tmp = [...cal];
    v.map(el => {
      for(let i=0; i<tmp.length; i++) {
        while(tmp[i]===el) {
          tmp.splice(i-1, 3, op(tmp[i-1], tmp[i+1], tmp[i]));
        }
      }
      // console.log(el, tmp);
    })
    // console.log(tmp);
    answer = Math.max(answer, Math.abs(tmp[0]));
  });

  return answer;
}

console.log(solution("100-200*300-500+20"));

배열 중간에 요소를 추가/삭제할 때 모두 splice()를 사용한다.
삭제하려면 arr.splice(idx, 삭제할 개수);
추가하려면 arr.splice(idx, 삭제할 개수, 추가할 요소);

다른 풀이

재귀

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)
  );
}

console.log(solution("100-200*300-500+20"));

function solution(expression) {
  const myLife = {
    // 잠시만요!
    "*": "✋",
    // 커피한잔?
    "+": "☕",
    // 어떠세요?
    "-": "❓",
    // 뭐라구요?
    "❓": "-",
    // 커피?
    "☕": "+",
    // 싫어요!
    "✋": "*",
  }
  const e = expression.replace(/\D/g, (m) => myLife[m])
  return priority([...new Set(e.match(/\D/g))])
    .map((v) =>
      v.reduce((pre, cur) => {
        while (pre.includes(cur)) {
          const target = pre.match(new RegExp(`-?\\d+${cur}-?\\d+`))
          pre =
            pre.substring(0, target.index) +
            eval(target[0].replace(/[^-\d+]/g, (m) => myLife[m])) +
            pre.substring(target.index + target[0].length)
        }
        return pre
      }, e)
    )
    .reduce((pre, cur) => (pre <= Math.abs(cur) ? Math.abs(cur) : pre), 0)
}

function priority(symbols) {
  if (!symbols.length) return [[]]
  return symbols.reduce(
    (pre, cur, idx, arr) =>
      pre.concat(
        priority([...arr.slice(0, idx), ...arr.slice(idx + 1)]).map((v) => [
          cur,
          ...v,
        ])
      ),
    []
  )
}

console.log(solution("100-200*300-500+20"));