[JS] 수식 최대화

뭔가 이문제는 되게 쉬워보이는데 잘 안되는것 같죠..?

몇 번 시간 복잡도에서 걸리다보니까 괜히 반복문 여러개 쓰면 안될거 같고, 죄짓는 것 같은 이 느낌....

그래도 뭐 통과는 되니까 한번 해보죠!

어떻게 푸셨나요? 같이 한번 보죠!

---

문제 요약

expression	result
"100-200*300-500+20"	60420
"50*6-3*2"	300

• 나눗셈은 없습니다. 사칙 연산 *, +, -만 존재합니다.
• 적절히 사칙연산의 순서를 조정해서 절댓값이 가장 큰 값을 return 합니다.

문제 해석

만약 첫번째 예시를 숫자배열, 기호 배열로 나누면 어떻게 될까요?

numbers = [100, 200, 300, 500, 20]

operators = [-, *, -, +]

이렇게 되네요.

 

우선 순위를 정한 다음 계속 연산 결과값으로 각 배열을 업데이트 해준다면 답을 얻을 수 있을 것 같습니다.

예를 들어, -가 1순위라고 했을때,

 

numbers = [-100, 300, 500, 20]

operators = [*, -, +]

 

numbers = [-100, -200, 20]

operators =  [*, +]

 

이런식으로요. 모든 loop가 끝난다면 numbers 배열에는 딱 1요소만 남게 되겠네요.

자 해봅시다!

 

정답 코드

function permutations(opers, level) {
    if (level === 1) return opers.map(v => [v]);
    const result = [];
    opers.forEach((fixed, i, arr) => {
        const rest = arr.filter((_, ai) => i !== ai);
        const combis = permutations(rest, level - 1);
        const perms = combis.map(v => [fixed, ...v]);
        result.push(...perms);
    });
    return result;
}

function solution(expression) {
    const numbers = expression.split(/[-*+]/).map(v => Number(v));
    const operStack = [];
    for (const letter of expression) {
        if (["-", "+", "*"].includes(letter)) {
            operStack.push(letter);
        }
    }
    
    const orders = permutations([...new Set(operStack)], [...new Set(operStack)].length);
    const result = [];
    
    orders.forEach((order) => {
        let tempOpers = [...operStack];
        let tempNumber = [...numbers];
        for (const operator of order) { 
            while (tempOpers.includes(operator)) {
                const index = tempOpers.indexOf(operator);
                const rest1 = tempNumber.slice(0, index);
                const rest2 = tempNumber.slice(index + 2);
                
                if (operator === "-") {
                    tempNumber = [...rest1, tempNumber[index] - tempNumber[index + 1], ...rest2];
                } else if (operator === "*") {
                    tempNumber = [...rest1, tempNumber[index] * tempNumber[index + 1], ...rest2];
                } else {
                    tempNumber = [...rest1, tempNumber[index] + tempNumber[index + 1], ...rest2];
                }
                tempOpers.splice(index, 1);
            }
        }
        result.push(Math.abs(tempNumber[0]));
    });
    return Math.max(...result);
}

 

팁1. replace를 여러 기호 기준으로 사용하는 방법.

정규표현식을 이용하면 인생 쉬워집니다.

const numbers = expression.split(/[-*+]/).map(v => Number(v));

슬래쉬 사이에 원하는 기호를 저런식으로 넣어주면 됩니다.

그리고 당연한 이야기지만 split을 한 다음 모든 요소는 string이 되기 때문에 Number나 parseInt 함수로 number 형식으로 바꿔줍시다!

 

팁2. 순열을 만드는방법.

이 문제는 각 기호에 대한 순열을 만들어서 순서를 정해줍니다. 전 그걸 orders에 넣어줬구요.

순열, 조합 생성하는 방법은 그냥 외워버렸습니다. 다음에 따로 한번 뽀개서 공유드릴게요. 일단 순열은 이걸 이용하시면 됩니다.

아 그리고 expression에서 추출한 연산 기호를 그대로 넣으시면 안되는거 아시죠...? set으로 중복을 제거하고 넣어줍시다!

function permutations(opers, level) {
    if (level === 1) return opers.map(v => [v]);
    const result = [];
    opers.forEach((fixed, i, arr) => {
        const rest = arr.filter((_, ai) => i !== ai);
        const combis = permutations(rest, level - 1);
        const perms = combis.map(v => [fixed, ...v]);
        result.push(...perms);
    });
    return result;
}

 

그리고.....

잘 보시면 반복문이 3중으로 중첩되어 있습니다.

• loop1 : 사칙 연산 순서를 담아둔 순열 배열(ex. [[-, +, *], [-, *, +].......])을 순회
  • loop2: 사칙 연산 순서를 순회
    • loop3: expression에서 분리한 사칙연산 순회

 

생각해보니 그나마 loop1, loop2의 개수가 몇개 안되어서 그냥 넘어갈만 한 것 같기도 합니다. 연산 기호가 많아봐야 3개니까요. 분리된 사칙연산의 갯수를 n이라 하면 18n이 최대네요.

 

뭔가 진짜 저걸 다 뽀개서 하는건가...?

하는 의심이 들어서 다른 방법 생각하다가 오래걸렸네요. 생각보다 쉬웠습니다.

 

그럼 이만!