수식 최대화

2020 카카오 인턴십

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

실행 결과 : 실패

---

문제를 이해하는 것은 어렵지 않다.

그런데 구현에서 자꾸 정답이 나오지 않았다... 답답했다.

 

설계는 어렵지 않으니 생략하고 왜 정답이 나오지 않았는가 정리해보겠다.

정답 코드는 다음과 같다.

function format(expression) {
    const ret = [];
    let tmp = '';
    [...expression].forEach((char)=>{
        if(!Number.isNaN(Number(char))) tmp += char;
        else{
            ret.push(tmp);
            tmp = "";
            ret.push(char);
        }
    });
    if(tmp.length) ret.push(tmp);
    return ret;
}

function calc(expression, priorArr){
    const expArr = format(expression);
    priorArr.forEach((prior)=>{
        expArr.forEach((char)=>{
            while(expArr.includes(prior)) {
                const idx = expArr.indexOf(prior);
                expArr.splice(idx - 1, 3, eval(expArr.slice(idx - 1, idx + 2).join("")));
            }
        });
    });
    return Math.abs(Number(expArr[0]));
}

function solution(expression) {
    let ret = Number.MIN_SAFE_INTEGER;
    const priorities = [
        [ '+', '-', '*' ],
        [ '+', '*', '-' ],
        [ '-', '+', '*' ],
        [ '-', '*', '+' ],
        [ '*', '+', '-' ],
        [ '*', '-', '+' ]
    ];
    priorities.forEach((prior)=>{
        ret = Math.max(ret, calc(expression, prior));
    });
    
    return ret;
}

 

오답코드와 정답코드의 차이는 calc 함수 로직이었다.

우선순위 기호가 없을 때까지 반복문을 수행하는 것과 달리 우선순위 기호가 있는 인덱스에 접근하는 방법은 splice를 사용하기 때문에 원본배열에 변화가 생겨 오답이 나온다. 

 

구체적인 예시는 다음과 같다.

우선 순위가 *, +, - 순서라고 가정할 때, 100 * 200 * 300 * 5 + 20 이라는 수식이 있다.

오답코드의 방법은 100 * 200 을 수행하고 20000 * 200 * 300 * 5 + 20 을 수행한다.

그리고 20000 * 200을 수행하여 4000000 * 300 * 5 + 20을 수행한다.

그런데 인덱스는 2를 가리키게 된다. splice로 인해 원본배열에 변화가 생겼기 때문이다.

* 연산을 더해야함에도 불구하고 인덱스 2인 200을 가리키기 때문에 *연산을 하지 않고 넘어가게된다.

 

따라서 splice와 같이 원본배열에 변화를 일으키는 코드가 있다면 인덱스에 접근해서 처리하는 로직이 맞는지 확인해야한다.

function calc(expression, priorArr){
    const expArr = format(expression);
    priorArr.forEach((prior)=>{
        expArr.forEach((char)=>{
            while(expArr.includes(prior)) {
                const idx = expArr.indexOf(prior);
                expArr.splice(idx - 1, 3, eval(expArr.slice(idx - 1, idx + 2).join("")));
            }
        });
    });

function calc(expression, priorArr){
    const expArr = format(expression);
    priorArr.forEach((prior)=>{
        expArr.forEach((char, idx)=>{
            if(char === prior) { // ❌
                expArr.splice(idx - 1, 3, eval(expArr.slice(idx - 1, idx + 2).join("")));
            }
        });
    });