문제

https://school.programmers.co.kr/learn/courses/30/lessons/67257
"100-200*300-500+20" 라는 식이 있다고 하자.
위의 식은 연산자의 우선순위가 달라지면 결과도 달라진다.
이 때 절댓값이 가장 큰 결과를 구하는 문제다.

입력: expression

• expression: 길이가 3이상 100이하인 문자열
  • 공백문자, 괄호문자 없이 (+, -, *)와 숫자만으로만 이뤄짐
  • 잘못된 연산식은 입력으로 주어지지 않음
    • 예를들어 "402+-561*"와 같은 수식
  • 피연산자는 음수가 포함되지 않음
  • 피연산자는 0이상 999이하의 숫자임
  • 적어도 1개 이상의 연산자를 포함하고 있음
  • 중간 계산값과 최종 결과는 무조건 절댓값이 $2^{63}$-1 이하임
  • 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높음

출력: 가장 큰 절댓값

접근

우선 모든 경우의수로 접근하면 바로 풀릴거라 생각했다.
그래서 우선 연산자와 피연산자를 추출했다.
그 후 추출한 연산자의 조합을 비교한다.

비교해서 연산자가 같다면 계산 후 결과를 피연산자가 들어있는 배열에 다시 넣어준다.
그 후 사용한 연산자는 제거한다.
그리고 연산자가 들어있는 배열이 비었다면 위의 과정을 그만한다.

전체코드

function solution(expression) {
    const combi = [
        ["+", "-", "*"],
        ["+", "*", "-"],
        ["-", "+", "*"],
        ["-", "*", "+"],
        ["*", "+", "-"],
        ["*", "-", "+"],
    ];
    
    const nums = expression.split(/[*|+|\-]/g).map(Number);
    let signs = expression.split(/[0-9]/g).filter( v => v !== "");
    let bigNum = 0;
    
    combi.forEach( signs => {
        let numsArr = nums;
        let signsArr = signs;

        signs.forEach( sign => {
            // 연산자를 모두 사용할 때 까지 while문 돌림
            while(signsArr.indexOf(sign) !== -1) {
                for (let i=0; i< signsArr.length; i++) {
                  	// 현재 배열의 연산자가 우선순위의 연산자라면
                    if (signsArr[i] === sign) {
                      	// i, i+1의 숫자를 연산해준다.
                        const calcNum = calc(numsArr[i], numsArr[i+1], sign);
                      	// 연산한 숫자를 합쳐서 배열에 넣어준다.
                        numsArr = [
                            ...numsArr.slice(0, i),
                            calcNum,
                            ...numsArr.slice(i+2, numsArr.length)
                        ];
                      	// 방금 사용한 연산자는 제거후 배열을 다시 만든다.
                        signsArr = [
                            ...signsArr.slice(0, i),
                            ...signsArr.slice(i+1, signsArr.length)
                        ];
                        break;
                    }
                }
            }

        });
        bigNum = Math.max(bigNum, Math.abs(numsArr[0]));
    });
    return bigNum;
}
function calc(num1, num2, sign) {
    if (sign === "*") return num1 * num2;
    if (sign === "+") return num1 + num2;
    if (sign === "-") return num1 - num2;
}

풀이시간

1시간