[programmers] 수식 최대화 - 2020 카카오 인턴십 (in JS)

문제

수식 최대화 - 2020 카카오 인턴십

• 1개 이상 3개 이하의 연산자가 반드시 속해있으며 연산자는 *, -, +인 수식이 주어진다.
• 해당 수식의 우선순위를 정의할 수 있다.
• 우선순위가 동등할 수는 없다.
• 우선순위에 따라 계산한 수식 중 최대값을 구하여라.
• 수식의 결과는 절댓값을 기준으로 결정한다.

Fact

• 수식은 스트링으로 주어지므로, 숫자와 연산자를 구분하여 나누어야 한다.
• k개의 연산자가 사용되었다면, 가능한 경우의 수는 k!이다.
• 가능한 연산자의 우선순위는 연산자들의 순열로 구할 수 있다.
• 어떠한 우선순위를 정하였을 때, 가장 큰 값이 나올지 알 수 없으므로 가능한 모든 경우의 수를 따져봐야 한다.

접근

1. 먼저 연산자의 순열을 구하여 가능한 모든 우선순위를 구한다.
2. 스트링으로 된 수식을 숫자와 연산자로 나눈 배열로 바꾼다.
   '100+20' => ['100', '+', '20']
3. 가능한 우선순위를 바탕으로 수식을 계산한 값 중 가장 큰 값을 반환한다.
   • 연산자를 수식에서 찾았으면, 연산자의 왼쪽과 오른쪽에 있는 숫자로 값을 계산한다. 이 때, eval함수로 값을 계산하고, 계산된 값을 수식에 넣는다.
   • 연산자가 수식에 없으면, 다음 우선순위의 연산자를 찾아서 위의 과정을 반복한다.
   • 마지막에 남은 수식이 우선순위에 따라 계산한 결과이다.

복잡도

• 공간 복잡도 : O(N)
  • 수식을 배열로 변경할 때, 수식의 길이에 따라 배열의 크기가 달라진다.
• 시간 복잡도 : O(N)

알게된 점

• 정규식에서 [^abc]는 a나 b나 c가 아닌 값을 파싱하여 가져오도록 한다.

• String.prototype.slice와 String.prototype.substring의 차이점

  1. indexStart가 indexEnd보다 클 경우
     • slice() : 빈 스트링을 반환한다.
     • substring() : 그 둘을 바꾸어서 계산한다.

     var text = "Mozilla";
     console.log(text.substring(5, 2)); // => "zil"
     console.log(text.slice(5, 2)); // => ""

  2. argument로 음수가 들어왔을 경우
     • slice() : 음수 인덱스를 뒤에서부터 계산한다. 가장 마지막 인덱스가 -1이다.
     • substring(): 음수를 0으로 처리한다.

     var text = "Mozilla";
     console.log(text.substring(-5, -2)); // => ""
     console.log(text.slice(-5, -2)); // => "zil"

• for ... of

  • for ... of는 반복 가능한 객체(iterable object)에 대해서 반복한다.
    반복 가능한 객체라는 것은 object나 prototype chain의 object중 하나가 Symbol.iterator key의 속성을 가져야 한다는 것이다.
  • 반복 가능한 객체는 Array, Map, Set, String, TypedArray, arguments 객체 등을 포함한다.

  for (const element of "abc") {
    console.log(element);
  }
  
  // expected output: "a"
  // expected output: "b"
  // expected output: "c"

코드

const makePriority = (candidate, priority, list) => {
  if (candidate.length === 0) {
    list.push(priority);
    return;
  }
  for (let i = 0; i < candidate.length; i++) {
    const newCandidate = candidate.slice(0, i) + candidate.slice(i + 1);
    const newPriority = priority + candidate[i];
    makePriority(newCandidate, newPriority, list);
  }
};

const getPriorityList = (expression) => {
  const priorityList = [];
  const candidate = [...new Set(expression.match(/[^\d]/g))];
  makePriority(candidate, "", priorityList);
  return priorityList;
};

const evalExpression = (priority, exp) => {
  let expression = [...exp];
  for (const op of priority) {
    while (expression.indexOf(op) !== -1) {
      const opIdx = expression.indexOf(op);
      const evaluatedExp = `${eval(
        expression.slice(opIdx - 1, opIdx + 2).join("")
      )}`;
      expression = [
        ...expression.slice(0, opIdx - 1),
        evaluatedExp,
        ...expression.slice(opIdx + 2),
      ];
    }
  }
  return Math.abs(+expression[0]);
};
function solution(expression) {
  const expList = expression.match(/\d+|[+\-*]/g);
  const priorityList = getPriorityList(expression);
  const answer = priorityList.reduce((maxResult, priority) => {
    const result = evalExpression(priority, expList);
    return Math.max(maxResult, result);
  }, 0);
  return answer;
}

소감

• 아직 iterable 객체에 대해서 잘 모르겠다. kojavascript에 iterable 객체 설명한 것이 있는데, 그걸 보고 이해하면 좋을 것 같다.
• evalExpression함수에서 arguments로 받은 exp를 새로운 배열에 할당하지 않고, 바로 값을 수정했었는데, solution에서 arguments로 넘겨준 배열에는 변화가 없었다. 배열은 argument로 넘겨주었을 때, 참조를 넘겨주기 때문에, 값이 변화할 줄 알았는데 변화가 없는 점은 왜그런지 모르겠다.
  arguments 객체가 무엇인지 알아봐야할 것 같다.
  -> argument의 exp가 같은 메모리를 참조하고 있다가, 참조하고 있던 값에 변경을 하는 것이 아니고, 다른 메모리에 새로운 배열을 할당하여 그것을 참조하는 것으로 하니, solution에 있는 배열은 그대로인 듯 하다.

expression = [ // 새로운 배열을 가리키도록 함.
  ...expression.slice(0, opIdx - 1),
  evaluatedExp,
  ...expression.slice(opIdx + 2),
];

• 정규식을 쓰면 코드가 훨씬 깔끔해지는 것 같다.