카카오 인턴쉽 문제: 수식 최대화

오랜만에 글을 작성해 본다. 

본 글은 카카오 인턴쉽 코딩테스트 문제 수식 최대화에 대한 해설을 담고 있으니, 스스로 풀고 싶으신 분이라면, 스포의 염려가 있으니 주의를 하시길 부탁드린다.

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

프로그래머스

문제에 대한 설명은 위의 링크를 참고하시면 된다. 핵심은 덧셈(+), 곱셈(*), 그리고 뺄셈(-) 중 어느 수식을 순서대로 먼저 계산을 해야 최대값(절대값)을 가질 수 있는지, 구하는 문제이다. 대부분 Lv.2 정도의 코딩 문제가 그렇듯, 모든 경우의 수를 다 구해서 이들 중 최적의 값(최대값)을 뽑아내면 된다.

 

 

1. 덧셈, 곱셈, 뺄셈 경우의 수 모두 구하기

문제는 +, *, - 중 어느 순으로 계산을 해야 최대값이 나오는지 물어보는 문제이다. 따라서, 3개의 연산자가 순서, 모든 경우의 수를 2차원 배열로 나타내면 다음과 같이 총 6개의 경우의 수가 있다:

[
  ['*', '+', '-'],
  ['*', '-', '+'],
  ['+', '*', '-'],
  ['+', '-', '*'],
  ['-', '*', '+'],
  ['-', '+', '*']
]

항목이 총 3개 밖에 안되니까, 이렇게 노가다를 하는 방식으로 모두 적어놓을 수는 있다. 어차피 문제에서도 연산자 항목이 3개만 주어지니, 사실 이렇게 2차원 배열을 만들어 놓고 풀어도 별다른 문제는 없을 것이다.

하지만, 항목이 5개, 6개 이렇게 늘어나게 된다면? 아마, 일일이 노가다를 하는 방식으로 적기 힘들 것이다. 중학교 시절에 순열문제를 풀어보신 적이 있으신가? 이 문제는 그 방식으로 접근해야 한다.

다음 아래는 (chatGPT의 힘을 빌려) 작성한 순열의 모든 경우의 수를 2차원 배열로 출력하는 함수이다.

function getPermutations(arr){
    let result = [];
    if(arr.length === 0) return [[]];

    for(let i=0; i< arr.length; i++){
        const fix = arr[i];
        const rest = arr.slice(0,i).concat(arr.slice(i+1));
        const permutations = getPermutations(rest);

        for(let p of permutations){
            result.push([fix, ...p]);
        }
    }
    return result;
}

만약 위와 같은 로직을 처음 접해보셨다면 이해가 안될 것이다. 그건 정상이다. 처음 접하는 로직은 몇 번이고 살펴보고 응용을 해야 그제서야 감이 잡히기 시작하니까...

로직에 대해 설명하자면, 먼저 arr로 순열을 만들 원재료인 배열 [ "+", "*", "-"]을 받는다. 다음 재귀함수를 통해 뎁스를 파게 된다. 뎁스를 팔 때마다, fix라는 곳에 3개의 연산자(항목)들 중 하나를 픽한 다음, rest 배열에 픽한 항목을 제외한 나머지를 집어넣어 다음 뎁스에 넘긴다.

대부분의 재귀함수가 그렇듯, 뎁스를 무한으로 팔 수 없다. 계속 항목을 픽을 하면, rest 배열은 빈 칸이 될 것이다. 이럴 경우, if 구문에서 빈 배열을 return하는 방식으로 뎁스가 끝난다.

이렇게 로직을 구성을 하면, 배열 [ "+", "*", "-"]을 통해 총 6개의 순열이 만들어진다.

 

 

2. 본격적으로 수식 구문을 연산하기

문제에서 수식 구문은 문자열로 작성되어 있다. 예를 들어 문자열 "100-200*300-500+20" 이 있다면, 이를 각각 나눠서 숫자로서 계산을 해야 한다. 방법은 다양하게 있겠으나, 저의 경우 Javascript의 split을 이용하여, 각 요소를 쪼개어 배열로 만드는 작업을 하였다.

let spilted = expression.split(/(-|\+|\*)/);

이렇게 작성할 경우, 다음 아래와 같이 배열이 만들어진다:

100

-

200

*

300

-

500

+

20

그런 다음 어떻게 해야 할까? 계산을 해야 한다. 예를 들어 곱셈을 먼저 계산을 한다고 해보자. 그럼 위의 배열은 다음 아래와 같이 다시 만들어져야 한다

100

-

60000

-

500

+

20

그리고 뺄셈을 한다? 그러면 뺄셈이 적용된 다음 배열, 덧셈을 하면, 덧셈을 적용한 다음 배열이 나와, 최종으로는 하나의 값으로 축약되어야 한다.

저는 이 로직을 다음 아래와 같이 작성을 하였다.

function calculation(operation, splitedArr){
    let calculatedArr = [];
    for(let i=0; i < splitedArr.length; i++){
        if(operation==splitedArr[i]){
            const caled = calc(calculatedArr[calculatedArr.length-1], splitedArr[i], splitedArr[i+1]);
            calculatedArr.pop();
            calculatedArr.push(caled);
            i++;
        }else{
            calculatedArr.push(splitedArr[i]);
        }
    }
    return calculatedArr;
}

function calc(a, op, b){
    switch(op){
        case "*":
            return (+a)*(+b);
        case "-":
            return (+a)-(+b);
        case "+":
            return (+a)+(+b);
        default:
            return null;
    }
}

operation은 연산자이고, splitedArr는 문자열 "100-200*300-500+20" 따위를 배열로 만든 것을 말한다. for 문으로 배열을 한번 씩 순회하며, operation에 넣은 연산자와 동일한 연산자가 나올 경우, 이를 계산을 하여, calculatedArr에 집어넣는다. 

함수 calc은 배열 속 요소도 결국 문자열이기 때문에, 이를 숫자로서 계산을 하기 위해 만든 함수이다.

무엇보다 해당 calculation 함수는 1회만 작동이 가능한 상태이다. 그러니까 배열 [100, -, 200, *, 300, -, 500, +, 20]에서 operater에 *을 넣으면, calculatedArr는 곱셈만 계산을 한 [100, -, 60000, -, 500, +, 20] 만 출력하고 끝난다.

이를 개선하기 위해선, 연산자 종류가 3개 밖에 없으니 calculation 함수를 3번 돌리는 방법도 있으나, 좀 더 깊이있게 풀기 위해 저는 재귀함수를 활용하였다.

 

 

3. 수식 구문을 재귀함수로 자동화하기

재귀함수 calculationRecur를 작성하였다. 함수 구조는 아래와 같다:

function calculationRecur(order, arr, indx){
    if(indx >= order.length){
        return arr;
    }
    const calcArr = calculation(order[indx], arr);
    indx++;
    return calculationRecur(order, calcArr, indx);
}

해당 함수는 order라고 하는 연산자 배열을 받는다. 예를 들어, order가 [ "+", "*", "-"]라면 덧셈-곱셈-뺄셈 순으로 계산을 하는 것이다.

indx는 인덱스이며 처음에는 0으로 시작한다. 추후 뎁스가 나아갈 때마다 1++ 하여 마침내 order 배열 길이인 3만큼 파게 되면 중단된다. 매 뎁스마다 calculation함수를 호출하여 계산을 하며, order 배열의 indx의 값을 기준으로 연산을 한다.

 

 

4. 최종 식은 다음 아래와 같다

이렇게 하여 완성된 최종 식은 다음 아래와 같다:

function solution(expression) {
    let spilted = expression.split(/(-|\+|\*)/);

    function calculationRecur(order, arr, indx){
        if(indx >= order.length){
            return arr;
        }
        const calcArr = calculation(order[indx], arr);
        indx++;
        return calculationRecur(order, calcArr, indx);
    }
    
    function calculation(operation, splitedArr){
        let calculatedArr = [];
        for(let i=0; i < splitedArr.length; i++){
            if(operation==splitedArr[i]){
                const caled = calc(calculatedArr[calculatedArr.length-1], splitedArr[i], splitedArr[i+1]);
                calculatedArr.pop();
                calculatedArr.push(caled);
                i++;
            }else{
                calculatedArr.push(splitedArr[i]);
            }
        }
        return calculatedArr;
    }
    
    function calc(a, op, b){
        switch(op){
            case "*":
                return (+a)*(+b);
            case "-":
                return (+a)-(+b);
            case "+":
                return (+a)+(+b);
            default:
                return null;
        }
    }   
    
    function getPermutations(arr){
        let result = [];
        if(arr.length === 0) return [[]];
        
        for(let i=0; i< arr.length; i++){
            const fix = arr[i];
            const rest = arr.slice(0,i).concat(arr.slice(i+1));
            const permutations = getPermutations(rest);
            
            for(let p of permutations){
                result.push([fix, ...p]);
            }
        }
        return result;
    }
    
    let answer = 0;
    const order = ["*", "+", "-"];
    const allCases = getPermutations(order);
    for(let order of allCases){
        const res = Math.abs(calculationRecur(order, spilted, 0));
        if(res > answer){
            answer = res;
        }
    }

    return answer;
}

모든 테스트 케이스를 통과하였으며, 속도 면에서도 지장이 없었다.

순서는

1. 더하기, 빼기, 곱하기 이 세가지 연산자로 모든 순열(경우의 수)를 구한다.

2. 각 순열에 맞춰 문자열을 배열로 만들어 계산을 한다.

3. 결과(절대값)이 기존 값보다 클 경우, 현재 값으로 치환한다.

라고 하면 되겠다!