[프로그래머스] 2020 카카오 인턴십 _ 수식 최대화 (도른자)

2021_08_08 스터디 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/67257?language=javascript# 

코딩테스트 연습 - 수식 최대화

문제

 

이 문제도 도른놈이었다.

난이도별로 점진적으로 스터디 문제를 풀고 있다 보니 이제 온통 어려운 것들만 만나고 있다.

머리가 녹는다는 게 이런 기분일까

---

우선 수도코드를 작성하기 전 문제를 탐색 했다. string타입의 expression 매개변수가 주어지는데, 이것을 어떻게 계산할 것인가?

연산 부호의 위치를 구한다 해도 몇자리일 지 모르는 숫자를 양옆에서 찾아 체크를 하는 건 너무 비효율 적이라 생각했고, 그런 부분을 문제에서 바랄 것 같진 않다고 생각했다.

string 형식으로 표현된 계산식을 자바스크립트에서 number 타입으로 계산할 수 있는 지에 대해 구글링을 해보니 스택오버플로우에 좋은 글이 있었다.

https://stackoverflow.com/questions/6479236/calculate-string-value-in-javascript-not-using-eval

Calculate string value in javascript, not using eval

eval 메소드를 통해서 string 타입의 연산식을 숫자 타입으로 계산한 반환값으로 받을 수 있다.

1차적인 큰 고민은 해결되어 이를 또 어떻게 해결할 것인가에 대해 수도코드를 작성하기 시작했다.

 

1 ~ n차 수도코드

// 1.  expression에 연산 부호가 있는 지 먼저 체크하고 있는 연산부호를 담는다
    // expression을 순회하면서, '-', '+', '*' 중 하나 이고, operator 배열에 포함되어 있지 않다면, operator에 추가

// 2. operator에 있는 것으로 우선순위 조합을 만들어 내야 함. 그 조합을 토대로 순회하면서 진행

// 3. expression에서 조합[i]가 위치한 곳을 모두 찾고 양쪽 연산자, 피연산자를 계산해야 함
    // 어떻게 추출할 것인가?

    // expression을 순회
        // 연산자가 나올 경우 그 연산자들을 순서대로 저장한다 ex) ["-", "+", "-", "*"] > sotredOperator
        // expression[i] = ','로 변경한다
    // expression을 ','로 쪼갠다 splitedExpression
    

    // sotredOperator를 순회
        // sotredOperator[j]가 조합 [i]와 같다면, 
            // splitedExpression[j]는 연산자
            // splitedExpression[j + 1]는 피연산자
            // 두 대상에 괄호를 씌워준다

                // splitedExpression[j] = "(" + splitedExpression[j] , ex) "(100"
                // splitedExpression[j + 1] = splitedExpression[j + 1] + ")" , ex) "200)"
                // 괄호를 씌운 것들을 따로 빼내어 eval로 계산? 
                // let temp = eval(splitedExpression[j] + splitedExpression[j + 1])
                // 

            
            // 중복되는 경우 어떻게 핸들링?
                // 계산을 한 번 하고나면 splitedExpression이 새로 만들어져야 함?

// 3. 우선 순위대로 괄호를 넣고 eval로 계산한 것을 다시 newExpression으로 재할당

보다 싶이 수도코드인데도 정리가 하나도 되지 않았다. 애초에 수도코드의 상태가 정상적인 코드를 구현하는 방법과는 거리가 멀다고 판단했고, 머리를 더 쥐어짜다가 문제에 대한 설명을 블로그에서 찾아보았다.

https://grapetown.tistory.com/63

[2020 카카오 인턴십 / 프로그래머스] 수식 최대화 완벽 풀이 - 파이썬(Python3)

코드는 참고하지 않았으나, 알고리즘 부분에 대한 설명을 보며 흩어져있던 아이디어들을 다시 모을 수 있었고, 이를 토대로 다시 수도코드를 작성했다. 

 

마지막 수도코드

// 1.  expression에 연산 부호가 있는 지 먼저 체크하고 있는 연산부호를 담는다
    // expression을 순회하면서, '-', '+', '*' 중 하나 이고, operator string에 포함되어 있지 않다면, operator에 더해준다
    //  operator의 조합

// 2. operators 있는 최대 경우의 수로 작업 
// const Alloperators = ["+-*", "+*-", "-+*", "-*+", "*+-", "*-+"] 최대 6가지 

// const validOperators = Alloperators를 map으로 순회하면서, 갖고 있지 않은 operator를 replace를 사용, 빈문자열로 교체
    // oprator를 순회한다
        // 만약, operator[i]가 el에 포함되어있지 않다면, el.replace(operator[i], "")을 리턴한다
    // 순회가 끝난 경우 (모두 있는 경우) el을 그대로 리턴한다


// let result = []
// validOperators 를 순회한다.
    // 만약 validOperators[i]의 길이가 1인 경우 eval(expression)의 값을 Result에 넣고 반복문 종료

    // (이제 유효한 연산부호가 2개 이상인 경우)
    // let speratedExpression =  validOperators[i][validOperators.length - 1](마지막 요소)로 expression을 split으로 쪼갬

    // 만약 validOperators[i]의 길이가 2인 경우
        // let tempResult = speratedExpression.map 순회한다
            // el에 validOperators[i][0]이 있는 곳을 찾고, 그 대상에 괄호를 씌움
        // tempResult.join(validOperators[i][validOperators.length - 1]) 쪼개는 데에 사용한 연산부호를 다시 이어 붙인다음 eval로 계산하여 result에 넣어준다
    
    
    // 만약 validOperators[i]의 길이가 3일 경우,  
        // speratedExpression = speratedExpression.split(validOperators[i][1]) 두번째 요소로 expression을 쪼갬 (2차원 배열)
        // let tempResult = speratedExpression.map((el ) => ..) 순회
                // let secondTemp = el.map 또 순회
                    // validOperators[i][0]가 속한 곳을 찾고 괄호를 씌움
                // secondTemp.join(validOperators[i][1]) split 쪼갰던 걸 이어 붙인 것을 리턴한다
        // tempResult.join((validOperators[i][validOperators.length - 1])) (중간 순위) 이어 붙이고 eval로 계산하여 result에 넣어준다

// result.map 순회를 하면서 그 요소가 음수라면 -를 한 값으로 맵핑
// result에서 최댓값을 구해 리턴한다

 

코드

function solution(expression) {
    const Alloperators = ["+-*", "+*-", "-+*", "-*+", "*+-", "*-+"]
    
    let operator = "";
    
    for (let j = 0; j < expression.length - 1; j++) {
        if ((expression[j] === "-" || expression[j] === "+" || expression[j] === "*") && !operator.includes(expression[j])) {
            operator += expression[j];
        }
    }
    
    const validOperators = Alloperators.map((op) => {
        for (let i = 0; i < operator.length - 1; i++) {
            if (!op.includes(operator[i])) {
                return op.replace(operator[i], "")
            }
        }
        return op;
    })
    
    let result = [];
    
    validOperators.forEach((op) => {
        if (op.length === 1) {
            result.push(eval(expression));
            return;
        }
        let speratedExpression = expression.split(op[op.length - 1]);
        if (op.length === 2) {
            let tempResult = speratedExpression.map((el) => {
                if (el.includes(op[0])) {
                    return `(${el})`
                }
                return el
            })
            result.push(eval(tempResult.join(op[op.length - 1])))
        } else if (op.length === 3) {
            speratedExpression = speratedExpression.map((h) => h.split(op[1]))
            
            let tempResult = speratedExpression.map((el) => {
                let secondTemp = el.map((e) => {
                    if (e.includes(op[0])) {
                        return `(${e})`
                    }
                    return e;
                })
                return secondTemp.join(op[1]);
            })
            result.push(eval(tempResult.join(op[op.length - 1])))
        }
    })
    result = result.map((el) => el < 0 ? -el : el);
    return Math.max(...result)
}

 

우선 문제에서 사용되는 연산부호는 최대 3개이고, 3!의 값을 가지고 있기 때문에 따로 경우의 수 알고리즘을 만들기보다는 최대 경우의 수를 구하고, 그 경우의 수에서 expression에 존재하지 않는 연산부호를 제거하면서 유효한 경우의 수로 다시 만들어냈다. 

우선순위로 조합된 validOperator를 제일 우선순위가 낮은 것들로 split 메소드를 사용 쪼갠 후 제일 중요한 애를 살려두고 괄호로 묶는 방법을 사용했다. 

이 경우 유효한 연산 부호가 갯수에 따라 배열의 깊이가 달라지는 문제가 있었고 이는 조건문으로 보완했다.

validOperator[i]의 길이가 1인 경우 1개의 연산자만 사용된 것, 바로 eval 메소드로 계산한 값을 result 에 담는다.

validOperator[i]의 길이가 2인 경우 2개의 연산자만 사용, 1차원 배열로 처리 가능

validOperator[i]의 길이가 3인 경우 모든 연산자 (3개) 사용, 2차원 배열로 처리 가능

최종적으로 모두 처리가된 아이들을 join으로 제거한 연산부호들을 넣어 연결해준 뒤 eval로 계산해서 result에 넣은 다음 최댓값을 구하는 코드이다.

테스트케이스 통과해서 신난 마음에 춤추며 채점을 했는데 56.7점이었다.

테스트케이스를 추가해보았음에도 어떤 부분에서 문제가 발생하는 것인지 찾지 못하고있다.

이것도 통과할 때까지 기간을 좀 잡고 여러번 풀어볼 생각이다. 대체 왜 안돼~~~~~~~~