[Leetcode/C++] 241_Different Ways to Add Parentheses

문제는 다음과 같습니다.

식이 주어지면, 연산자의 순서를 지정하여
모든 연산의 가능한 경우의 수를 구하는 게 문제의 포인트입니다.

저는 먼저, 임의의 한 연산자에 중심으로 양쪽에 대해서 분할 정복을 통한 재귀로 문제를 풀었습니다.

가장 먼저 호출되는 main stack에서
for문을 돌릴 때,
해당 연산자를 기준으로 양쪽에 대해 분할정복을 통한 재귀로 나올 수 있는 모든 경우를 구한 뒤,
그 연산자를 기준으로 연산을 수행합니다.

main stack에서 돌려지는 for문에서
즉, exp[i]는 해당 연산자가 마지막에 수행되는 경우를 의미합니다.
(즉, 양쪽에 대한 모든 연산을 수행한 뒤, exp[i]의 연산이 수행되는 것입니다.)

전체 코드는 다음과 같습니다.

class Solution {
public:
    vector<int> diffWaysToCompute(string exp) {
        vector<int> res;
        
        for(int i=0; i<exp.size(); i++){
            
            if(exp[i]=='+' || exp[i]=='-' || exp[i]=='*'){
                string s1 = exp.substr(0, i); string s2 = exp.substr(i+1);
                vector<int> v1 = diffWaysToCompute(s1); vector<int> v2 = diffWaysToCompute(s2);
                
                for(int j=0; j<v1.size(); j++){
                    for(int k=0; k<v2.size(); k++){
                        if(exp[i]=='+') res.emplace_back(v1[j]+v2[k]);
                        else if(exp[i]=='-') res.emplace_back(v1[j]-v2[k]);
                        else res.emplace_back(v1[j]*v2[k]);
                    }
                }
            } // if문 끝
            
        }
        
        if(res.size()==0) res.emplace_back(stoi(exp));
        return res;
    }
};