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

프로그래머스 [카카오 인턴] 수식 최대화 [KAKAO]

카테고리 : 문자열

풀이과정은 다음과 같다.

1) 문자열 파싱

연산자와 숫자를 분리해 배열을 만든다.

operator: ['+','-','*']
number : ['100','200','300']

2) 수식 우선순위를 결정

백트래킹을 활용해 수식의 우선순위를 결정한다.
연산자가 3개이기에 직접 연산자 배열을 만들어도 될 것같다.

3) 수식 계산

우선순위 순대로 수식을 계산한다.
계산이 완료 된 number 배열의 원소와 operator 연산자는 삭제해준다.

배열이 다음과 같다고 하자.

['+','*','-']
[500,100,200,300]

우선순위 연산자가 '+' 일때, 연산 후 배열 상태는 다음과 같다.
   
['*','-']
[600,200,300]

주의할점은 연산자 배열을 기준으로 for문을 돌 때,
연산을 했다면 for문의 (증감 변수 -1)을 해줘야만
모든 연산이 완료된다.

소스 코드

function solution(expression) {
    let answer = 0;
    const check=[];
    const number=[];
    const operation=[];
    
    function parse(exp){
        let str="";
        for(let i=0;i<exp.length;i++){
            if(exp[i]!=='*' && exp[i]!=='-' && exp[i]!=='+'){
                str+=exp[i];
            }else{
                number.push(str);
                if(i!==0 && exp[i-1]>=0 && exp[i-1]<=9) operation.push(exp[i]);
                str="";
            }
            if(i===exp.length-1) number.push(str);
        }
        
        for(let i=0;i<number.length;i++){
         if(number[i]===""){
             number.splice(i,1);
             number[i]=-number[i];
         }   
        }
    }
    
    
    function calc(oper,num1,num2){
        if(oper==='+') return num1*1+num2*1;
        if(oper==='-') return num1*1-num2*1;
        if(oper==='*') return (num1*1)*(num2*1);
    }
    
    function numToOper(num){
        if(num==='0') return '+';
        if(num==='1') return '-';
        if(num==='2') return '*';
    }
    
    
    function deepCopy(a,b){
        for(let i=0;i<b.length;i++) a[i]=b[i];
    }
    
    
    function go(str){
        let num=[];
        let oper=[];
        
        deepCopy(num,number);
        deepCopy(oper,operation);
        
        for(let i=0;i<3;i++){
            let nowOper=numToOper(str[i]);
            for(let j=0;j<oper.length;j++){
                if(oper[j]===nowOper){
                    let result=calc(oper[j],num[j],num[j+1]);
                    num[j]=result;
                    oper.splice(j,1);
                    num.splice(j+1,1);
                    j--;
                }   
            }
        }
        return Math.abs(num[0]);
    }
    
    function command(cnt,order){
        if(cnt===3){
            answer=Math.max(answer,go(order));
            return;
        }
        
        for(let i=0;i<3;i++){
             if(check[i]) continue;
             check[i]=1;
             command(cnt+1,order+i);
             check[i]=0;
        }
    }
    
    parse(expression);
    command(0,"");
    
    return answer;
}

다른 사람의 코드

내 코드와 다른점
1) 연산자 배열을 직접 만들었다.
2) slplit 정규표현식을 활용해 expression 배열을 파싱했다.
3) deepCopy => slice()로 가능

const solution = (expression) => {
  const arr = [
    ["+", "-", "*"],
    ["+", "*", "-"],
    ["-", "+", "*"],
    ["-", "*", "+"],
    ["*", "+", "-"],
    ["*", "-", "+"],
  ];

  //1. 수식을 숫자(num)과 기호(sign)으로 나눈다.
  let num = expression.split(/[^0-9]/);
  num = num.map((it) => {
    return parseInt(it);
  });
  const sign = [];
  for (let i = 0; i < expression.length; i++) {
    if (
      expression[i] === "*" ||
      expression[i] === "+" ||
      expression[i] === "-"
    ) {
      sign.push(expression[i]);
    }
  }

  let maxNum = 0;
  for (let i = 0; i < arr.length; i++) {
    //2. 배열과 수식을 복사한다.
    const copyNum = num.slice();
    const copySign = sign.slice();
    for (let j = 0; j < arr[i].length; j++) {
      for (let k = 0; k < copySign.length; k++) {
        if (copySign[k] === arr[i][j]) {
          if (copySign[k] === "*") {
            copyNum[k] *= copyNum[k + 1];
            copyNum.splice(k + 1, 1);
            copySign.splice(k, 1);
            k--;
          } else if (copySign[k] === "+") {
            copyNum[k] += copyNum[k + 1];
            copyNum.splice(k + 1, 1);
            copySign.splice(k, 1);
            k--;
          } else {
            copyNum[k] -= copyNum[k + 1];
            copyNum.splice(k + 1, 1);
            copySign.splice(k, 1);
            k--;
          }
        }
      }
    }
    //3. 계산후에 최댓값과 비교하여 최댓값을 찾는다.
    if (Math.abs(copyNum[0]) >= maxNum) {
      maxNum = Math.abs(copyNum[0]);
    }
  }
  return maxNum;
};

다른 사람의 코드 - 2

const solution = (expression) => {
  const numbers = expression.split(/[^0-9]/).map(v => Number(v));
   /*
    ^x : x로 시작하는 문자.
    expression : 	"-100*-200"
   	result => numbers = 	[ 0, 100, 0, 200 ]
   */
  const operators = expression.split(/[0-9]/).filter(v => v);
	/*
	  result => operators = [ '-', '*-' ]
	*/
  const formula = getFormula(numbers, operators);
  const cases = [
    ['*', '+', '-'], ['*', '-', '+'], ['+', '*', '-'],
    ['+', '-', '*'], ['-', '+', '*'], ['-', '*', '+'],
  ];

  /*
  	...cases => 2차원 배열의 원소인 1차원 배열을 기준으로 탐색하기 위함.
  */
  return Math.max(...cases.map(operators => {
    let result = formula.slice();
    operators.forEach(operator => {
      result = computeByTargetOperator(result, operator);
    });

    return Math.abs(...result);
  }));
};

const getFormula = (numbers, operators) => {
  const formula = [];

  numbers.forEach((number, i) => {
    formula.push(number);

    if (operators[i]) {
      formula.push(operators[i]);
    }
  });

  return formula;
}

const computeByTargetOperator = (formula, targetOperator) => {
  const computation = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
  }

  const stack = [];
  for (let i = 0; i < formula.length; i += 1) {
    const target = formula[i];
    if (target === targetOperator) {
      const previousValue = stack.pop();
      const nextValue = formula[i + 1];

      const result = computation[targetOperator](previousValue, nextValue);

      stack.push(result);
      i += 1;
      continue;
    }

    stack.push(target);
  }

  return stack;  
};