안녕하세요

프로그래머스 JS [수식 최대화] 본문

프로그래머스/Lv.2

프로그래머스 JS [수식 최대화]

sakuraop 2022. 12. 21. 03:29

[카카오 인턴] 수식 최대화

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

[제한사항]
  • expression은 길이가 3 이상 100 이하인 문자열입니다.
  • expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
    • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
  • expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
    • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
    • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
  • expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
  • 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
  • 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.
입출력 예expressionresult
"100-200*300-500+20" 60420
"50*6-3*2" 300
풀이 순서

1. 숫자 배열과 연산자 배열 나누기

=> [ '100', '200', '300', '500', '20' ], [ '-', '*', '-', '+' ]


2. 특정 연산자에 대한 연산 시행하기 splice()를 활용한다.
            tempNumberArray.splice(currentOperatorIndex, 2, value);
            tempOperatorArray.splice(currentOperatorIndex, 1);

=> 연산을 시행하면 연산에 사용된 숫자 두 개는 결과로 바꾸고, 하나의 연산자를 제외한다.
[1,3,2], [+,-]
연산 결과로 바꾸기, 연산자 제외 
[4,2], [-]


3. 연산자 배열에 대해 조합을 생성한다.
    // =>[[ '*', '+', '-' ],
    //    [ '*', '-', '+' ],
    //    [ '+', '*', '-' ],
    //    [ '+', '-', '*' ],
    //    [ '-', '+', '*' ],
    //    [ '-', '*', '+' ]]


4. 연산자조합에 대해 연산을 모두 시행한다.


5. 절댓값으로 변환한 결과 중 가장 큰 수를 반환한다.



주석 달아놓은 코드
 
function solution(expression) {
    let numbers = "";
    let operators = "";

    // 숫자 배열과 연산자 배열 나누기
    // => [ '100', '200', '300', '500', '20' ], [ '-', '*', '-', '+' ]
    expression.split("").forEach((el) => {
        if (isNaN(el)) {
            operators += el;
            numbers += ",";
        } else {
            numbers += el;
        }
    });

    const expressionArray = [numbers.split(","), operators.split("")];

    // 특정 연산자에 대한 연산 시행하기
    const operate = (operator, numberArray, operatorArray) => {
        const tempNumberArray = [...numberArray];
        const tempOperatorArray = [...operatorArray];

        let flag = true;
        while (flag) {
            // 특정 연산자의 인덱스를 찾는다.
            // => [ '-', '*', '-', '+' ] -를 찾으면 0 반환, +를 찾으면 3반환
            const currentOperatorIndex = tempOperatorArray.indexOf(operator);
            // 특정 연산자가 존재하지 않으면 반복을 멈춘다.
            if (currentOperatorIndex === -1) {
                flag = false;
                continue;
            }
            // eval() 함수로 특정 연산자의 인덱스, 연산, 특정 연산자의 인덱스 +1 를 계산한다.
            // [ '100', '200', '300', '500', '20' ], [ '-', '*', '-', '+' ]
            // => 100 - 200
            const value = eval(tempNumberArray[currentOperatorIndex] + operator + tempNumberArray[currentOperatorIndex + 1]);
            // 계산에 사용된 두 숫자는 하나의 계산 결과로 바꾸고,
            // 계산에 사용된 연산자는 제거한다.
            // => [ -100, '300', '500', '20' ], [ '*', '-', '+' ]
            tempNumberArray.splice(currentOperatorIndex, 2, value);
            tempOperatorArray.splice(currentOperatorIndex, 1);
        }

        // 특정 연산자가 존재하지 않을 때까지 시행한 결과 배열을 반환한다.
        // => [[ -60420 ] []]
        return [tempNumberArray, tempOperatorArray];
    };

    // 최대 6가지 이므로 직접 배열을 써 넣는게 빠르지만
    // 확장성을 고려해 다른 연산자가 추가될 수 있도록 연산자 배열에 대해 조합을 생성한다.
    // =>[[ '*', '+', '-' ],
    //    [ '*', '-', '+' ],
    //    [ '+', '*', '-' ],
    //    [ '+', '-', '*' ],
    //    [ '-', '+', '*' ],
    //    [ '-', '*', '+' ]]
    const 연산자배열 = ["*", "+", "-"];
    const 연산자조합 = [];
    const permutation = (i, array) => {
        const tempArray = [...array];
        if (i === 2) {
            return 연산자조합.push(tempArray);
        }
        for (let j = i; j < tempArray.length; j++) {
            [tempArray[i], tempArray[j]] = [tempArray[j], tempArray[i]];
            permutation(i + 1, tempArray);
            [tempArray[i], tempArray[j]] = [tempArray[j], tempArray[i]];
        }
    };
    permutation(0, 연산자배열);

    // 계산이 진행되는 과정을 담을 배열을 생성한다.
    let currentArray = [...expressionArray];
    const answer = [];

    // 연산자조합에 대해 모두 시행한다.
    연산자조합.forEach((el) => {
        // 각각의 연산자에 대해 시행한다.
        el.forEach((operator) => {
            const tempArray = operate(operator, currentArray[0], currentArray[1]);
            // 진행 과정을 저장한다.
            // => [ -100, '300', '500', '20' ], [ '*', '-', '+' ]
            currentArray = tempArray;
        });
        // 모든 연산자에 대해 수행한 결과를 담는다
        // => [[ -60420 ] []]
        answer.push(currentArray);
        // 원본 배열 형태로 복원한다.
        // => [ '100', '200', '300', '500', '20' ], [ '-', '*', '-', '+' ]
        currentArray = [...expressionArray];
    });

    console.log(Math.max(...answer.flat(2).map((el) => Math.abs(el))));
    // 절댓값으로 변환한 결과 중 가장 큰 수를 반환한다.
    // => [ 60420, 60380, 60420, 22000, 18000, 20020 ] 여기에 max()
    return Math.max(...answer.flat(2).map((el) => Math.abs(el)));
}

solution("100-200*300-500+20");
주석 제거한 코드

function solution(expression) {
    let numbers = "";
    let operators = "";

    expression.split("").forEach((el) => {
        if (isNaN(el)) {
            operators += el;
            numbers += ",";
        } else {
            numbers += el;
        }
    });

    const expressionArray = [numbers.split(","), operators.split("")];

    const operate = (operator, numberArray, operatorArray) => {
        const tempNumberArray = [...numberArray];
        const tempOperatorArray = [...operatorArray];

        let flag = true;
        while (flag) {
             const currentOperatorIndex = tempOperatorArray.indexOf(operator);
             if (currentOperatorIndex === -1) {
                flag = false;
                continue;
            }
            const value = eval(tempNumberArray[currentOperatorIndex] + operator + tempNumberArray[currentOperatorIndex + 1]);
          tempNumberArray.splice(currentOperatorIndex, 2, value);
            tempOperatorArray.splice(currentOperatorIndex, 1);
        }

        return [tempNumberArray, tempOperatorArray];
    };

    const 연산자배열 = ["*", "+", "-"];
    const 연산자조합 = [];
    const permutation = (i, array) => {
        const tempArray = [...array];
        if (i === 2) {
            return 연산자조합.push(tempArray);
        }
        for (let j = i; j < tempArray.length; j++) {
            [tempArray[i], tempArray[j]] = [tempArray[j], tempArray[i]];
            permutation(i + 1, tempArray);
            [tempArray[i], tempArray[j]] = [tempArray[j], tempArray[i]];
        }
    };
    permutation(0, 연산자배열);

    let currentArray = [...expressionArray];
    const answer = [];

    연산자조합.forEach((el) => {
        el.forEach((operator) => {
            const tempArray = operate(operator, currentArray[0], currentArray[1]);
            currentArray = tempArray;
        });
        answer.push(currentArray);
        currentArray = [...expressionArray];
    });

    console.log(Math.max(...answer.flat(2).map((el) => Math.abs(el))));
    return Math.max(...answer.flat(2).map((el) => Math.abs(el)));
}

solution("100-200*300-500+20");
저작자표시

'프로그래머스 > Lv.2' 카테고리의 다른 글

프로그래머스 JS [행렬 테두리 회전하기] 이차원배열의 깊은복사  (0) 2022.12.27
프로그래머스 JS [방금그곡]⭐문자열 다루기 idea 치환  (0) 2022.12.22
프로그래머스 JS [메뉴 리뉴얼]⭐⭐ 조합  (0) 2022.12.15
프로그래머스 JS [삼각 달팽이] array.flat() 배열평탄화  (0) 2022.12.14
프로그래머스 JS [큰 수 만들기] 탐욕법  (0) 2022.12.14
'프로그래머스/Lv.2' Related Articles more