괄호를 추가하는 서로 다른 방법

서론

❔ 문제

Leetcode 241, Different Ways to Add Parentheses 문제이다. 아래는 leetcode의 링크이다.
https://leetcode.com/problems/different-ways-to-add-parentheses/

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

숫자와 연산자로 이루어진 스트링 형식의 수식이 주어지면, 숫자와 연산자를 묶을 수 있는 모든 다른 경우의 수를 계산한 결과를 반환해라. 답은 어떤 순서이든 상관 없다.

이렇게 문제만 읽어서는 무슨 말인지 한번에 이해하기 어렵다. 예시를 보아야 한다.

Example 1:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

"2-1-1" 이라는 수식이 들어왔을때, 결과 값으로 0과 2를 반환해야 한다. Explanation을 보면 그 이유를 알 수 있다. 연산자에 괄호를 씌울 수 있는 방식이 두가지이기 때문이다.

Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

"2*3-4*5" 이라는 수식이 들어왔을 때, 결과 값으로 위의 다섯가지를 반환해야 한다. 이 output에는 -10이 두번 들어가 있는데, 같은 값이라 해도 괄호를 씌울 수 있는 방법이 두가지이기 때문이다.

제약 조건은 아래와 같다.

• 1 <= 수식의 길이 <= 20
• 수식은 숫자와, 연산자 '+', '-', '*' 로 구성되어 있다.
• input 수식의 모든 정수 값은 0부터 99까지이다.

🤔고민

처음 보면 문제가 일단 이해가 잘 되지않고 string 타입의 수식을 입력받는 것 조차도 고민이 된다. 가장 많이 생각했던 부분은, 어떻게 괄호를 씌울까? 이었다. for문을 돌려서 해결할지, 수식을 그래프에 넣어서 해결할지 고민을 했지만 두개 다 잘못된 접근이었다. 그러던 중 생각한 방식이 연산자를 중심으로 left, right를 탐색하는 것이었다. 이렇게 나눠서 생각을 하면 중복되는 케이스 없이 깔끔하게 계산이 되었다. 또한 여기서 시간을 줄이기 위해 dp를 사용한다. 수식이 길어질 수록 한번 계산했던 값을 또 계산하게 되기 때문에, dp 배열을 이용해서 시간을 단축한다.

코드

일단 내가 작성한 코드는 아래와 같다.

class Solution {
    public:
    vector<int> convert(string expression){
        //+ : -1 , - : -2, * : -3
        vector<int> exp;
        for(int i = 0; i<expression.size(); ){
            int t = int(expression[i]);
            int current; 
            if(0<=t-48 && t-48 <=9){
                if((i<=expression.size()-1)){
                    int tn = int(expression[i+1]);
                    if(0<=tn-48 && tn-48 <=9){
                        current = (t-48)*10+tn-48;
                        i+=2;
                    }
                    else{
                        current = t-48;
                        i++;
                    }
                }
                else{
                    current = t-48;
                    i++;
                }

            }
            else{
                switch(expression[i]){
                    case '+':
                        current = -1;
                        break;
                    case '-':
                        current = -2;
                        break;
                    case '*':
                        current = -3;
                        break;
                }
                i++;
            }
            exp.push_back(current);
        } 
        return exp;
    }
    int dp[101][101];
    vector<int>* dp_ptr[101][101];
    int convert_calc(int x, int op, int y){
        switch(op){
            case -1:
                return x+y;
            case -2:
                return x-y;
            case -3:
                return x*y;
        }
        return -1;
    }
    vector<int> calc(vector<int>& exp, int left, int right, vector<int> op_idx){
        if(left==right){
            vector<int> result;
            result.push_back(exp[left]); 
            return result;
        }
        if(!dp[left][right]){
            dp_ptr[left][right] = new vector<int>();
            for(int i = 0; i < op_idx.size(); i++){
                int target = op_idx[i];
                if(target<left || right<target)continue;
                op_idx.erase(op_idx.begin()+i);
                vector<int> t1 = calc(exp, left, target-1, op_idx);
                vector<int> t2 = calc(exp, target+1, right, op_idx);
                op_idx.insert(op_idx.begin()+i,target);
                for(int i = 0; i<t1.size(); i++){
                    for(int j = 0; j<t2.size(); j++){
                        dp_ptr[left][right] -> push_back(convert_calc(t1[i],exp[target],t2[j]));
                    }
                }
            }   
            dp[left][right] = 1;
            return *dp_ptr[left][right];

        }  
        else{
            return *dp_ptr[left][right];
        }
    }
    vector<int> diffWaysToCompute(string expression) {
        memset(dp,0,sizeof(dp));
        vector<int> exp = convert(expression);
        vector<int> op_idx;
        for(int i=0; i<exp.size(); i++){
            if(exp[i]<0)op_idx.push_back(i);
        }
        return calc(exp,0,exp.size()-1,op_idx);
    }
};

꽤 길지만 코드의 string의 수식을 vector로 변환하는 코드가 차지한다.

expression conversion

    vector<int> convert(string expression){
        //+ : -1 , - : -2, * : -3
        vector<int> exp;
        for(int i = 0; i<expression.size(); ){
            int t = int(expression[i]);
            int current; 
            if(0<=t-48 && t-48 <=9){
                if((i<=expression.size()-1)){
                    int tn = int(expression[i+1]);
                    if(0<=tn-48 && tn-48 <=9){
                        current = (t-48)*10+tn-48;
                        i+=2;
                    }
                    else{
                        current = t-48;
                        i++;
                    }
                }
                else{
                    current = t-48;
                    i++;
                }

            }
            else{
                switch(expression[i]){
                    case '+':
                        current = -1;
                        break;
                    case '-':
                        current = -2;
                        break;
                    case '*':
                        current = -3;
                        break;
                }
                i++;
            }
            exp.push_back(current);
        } 
        return exp;
    }

string 형식의 expression을 vector로 변환한다. 숫자의 범위는 0부터 99까지 이니 두자리 수가 나오는 경우도 고려해야한다.

" + : -1 , - : -2, * : -3 "

vector에 연산자는 위와 같이 음수 -1,-2,-3으로 저장한다. 따라서 vector의 값들을 계산할때는 아래의 함수가 필요하다.

    int convert_calc(int x, int op, int y){
        switch(op){
            case -1:
                return x+y;
            case -2:
                return x-y;
            case -3:
                return x*y;
        }
        return -1;
    }

예를 들어 위의 example 2의 경우, 수식은 2*3-4*5 이다. vector로 변환과정을 거치면 [2,-3,3,-2,4,-3,5] 이렇게 된다. 음수인 정수는 연산자에 해당된다. 23 을 계산하기 위해서는 *convert_calc(2,-3,3)** 을 호출해야 한다.

여기까지 하면 문제를 풀 준비가 끝난다.

calculation

풀이방식은 다음과 같다.

연산자를 중심으로 왼쪽과 오른쪽으로 나누어 다시 재귀호출을 한다. 이에 따라 나온 결과 값은 여러가지 일 수도 있기 때문에, dp 배열에 저장을 해 두었다가 왼쪽과 오른쪽의 계산이 끝나면 그 결과들을 계산한다.

Example 2를 예시로 들어보자.

2*3-4*5

이 수식에는 연산자가 세가지 있다. 앞에서 부터 순서대로 [ * , - , * ]이다.

처음 * 연산자를 기준으로 왼쪽 오른쪽을 나누면 2 와 3-4*5 이다. 왼쪽에서 얻을 수 있는 연산의 결과 값은 [2] 이다. 그리고 오른쪽에서 얻을 수 있는 결과 값은 다시 calc 함수를 재귀호출 해서 알아낸다. 그렇게 재귀호출을 하여 나올 수 있는 연산의 결과 값은 [-5,-17]이다. 따라서 * 연산자의 왼쪽 부분의 결과값 [2] 와 오른쪽 부분의 결과값 [-5,-17] 을 곱하면, [ * , - , * ] 여기서의 첫번째 요소 에 대한 계산이 끝난다. 이 작업을 모든 연산자에 대해서 수행하면 총 5가지가 나온다. 재귀 호출을 한다고 생각하면 아래와 같은 코드가 나온다.

int dp[101][101];
vector<int>* dp_ptr[101][101];

dp를 저장하기 위해 사용한 배열이다. dp는 main함수에서 0으로 초기화 된다. dp_ptr은 왼쪽과 오른쪽 부분의 결과 값을을 저장하기 위한 포인터 배열이다.

    // exp exp는 위에서 vector로 변환된 expression이다. left와 right는 현재 탐색하고 있는 expression의 index이다. op_idx는 operand, vector로 변환된 expression 에서 -1,-2,-3, 의 index이다. 
    vector<int> calc(vector<int>& exp, int left, int right, vector<int> op_idx){

        if(left==right){
            //기저 사례, left와 right의 index가 같다면 탐색이 끝난 것이다.
            vector<int> result;
            result.push_back(exp[left]); 
            return result;
        }

        if(!dp[left][right]){
            //dp의 값이 0인 경우는 계산을 한적이 없으므로 계산한다.
            dp_ptr[left][right] = new vector<int>();
            for(int i = 0; i < op_idx.size(); i++){
                int target = op_idx[i];
                if(target<left || right<target) continue;
                //탐색하는 부분에 있는 연산자의 index가 아닌 경우 continue한다.

                //연산자를 기준으로 왼쪽부분과 오른쪽부분의 값을 구하기 위해서 재귀호출 한다.
                op_idx.erase(op_idx.begin()+i);
                vector<int> t1 = calc(exp, left, target-1, op_idx);
                vector<int> t2 = calc(exp, target+1, right, op_idx);
                op_idx.insert(op_idx.begin()+i,target);

                //행렬의 곱을 수행하고, 탐색하는 부분의 결과 값을 dp배열에 저장한다.
                for(int i = 0; i<t1.size(); i++){
                    for(int j = 0; j<t2.size(); j++){
                        dp_ptr[left][right] -> push_back(convert_calc(t1[i],exp[target],t2[j]));
                    }
                }
            }   

            //dp를 최신화 해준다.
            dp[left][right] = 1;
            return *dp_ptr[left][right];

        }  
        else{
            //dp의 값이 0이 아닌 경우는 계산을 한적이 있으므로 그냥 그 값을 사용하면 된다.
            return *dp_ptr[left][right];
        }
    }

나는 꽤 복잡하게 풀이 했다. 다른 사람의 코드를 보았더니 풀이하는 방법을 똑같은데, string형식의 expression 을 변환하지 않고 그대로 사용했다. c++ 의 stringstream을 사용하면 변환하는 복잡한 작업 없이 쉽게 연산자와 숫자를 구분해서 사용할 수 있다. stringstream에 대해 정리하고 공부해두어야 겠다.