Expression Add Operators

분명 전에 풀었던 문제 같은데 솔루션을 보고 말았다 ㅠㅠ...Word에 꼭 저장해놓고 두고두고 봐야겠다.

재귀를 통해 + - * 를 할지는 구상을 했는데, 나는 3가지에 더해 후의 숫자를 추가로 붙이는걸 생각해 4가지로 생각했다.

이전 수가 1이고 지금 수가 2 라면 1+2, 1-2, 1*2 에다가 아예 붙여서 12 로 생각하는걸... 근데 그렇게 하지 않고 차라리 매 위치에서 for문을 돌려서  1 2 4 라면

1에서는 1에 3가지 연산, 12에 3가지 연산, 124가 끝이니 그대로 return

하는 방식을 사용해서 + - * 의 3가지를 매 단계에서만 생각하면 됐다.

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        //dfs실행
        dfs(num, 0, target, "", 0, 0, res);
        //결과 반환
        return res;
    }
private:
    //param 해석
    //1. &num: 문제에서 받은 배열 참조자로 넘기기
    //2. start: num배열에서 몇번째 문자부터 연산을 시작할 것인지. -> 1 2 4 이렇게 받았고 1까지는 처리했다면 start=1
    //3. target: 문제에서 받은 target그대로 넘기기
    //4. path: 현재까지 완성한 식
    //5. prev: 이전단계에서 연산에 사용한 값. 이전단계에서 1+2를 하여 3이 됐다면 2를 저장하고 있는다
    //6. cur: 이전단계에서 연산된 값. 이 값을 가지고 지금단계에서 연산할 지, 그대로 끝낼지 결정한다
    //7. res: 결과로 반환할 vec 넘겨서 정답을 저장하는 데에 사용
    void dfs(string &num, int start, int target, string path, long prev, long cur, vector<string> &res) {
        //마지막 값까지 사용하였고, 마지막 결과가 정답이라면 반환 vec에 저장한다.
        if(start == num.size() && prev + cur == target) res.push_back(path);

        //일단 1개의 숫자를 가지고 연산하는거부터 해서 수를 하나씩 더해가면서 계산한다 (1 2 4 -> 1처리, 12처리, 124 처리)
        for(int i = 1; start + i <= num.size(); i++) {
            //substr으로 문자열에서 start부터 i번째까지의 문자열을 자른다.
            string s = num.substr(start, i);
            //stoll: str을 long값으로 변환시켜준다.
            long n = stoll(s);
            //105의 경우 0부터 시작하여 값 2개를 뽑으면 05인데, long변환시 5가 된다. 이런 경우를 처리하기 위함.
            if(to_string(n).size() != s.size()) return;
            //아직 첫번째 숫자도 담지 않았다면 우선 첫번째 숫자를 담아서 다음 dfs로 보낸다. 이후부터는 아래 else문 진입
            if(!start) dfs(num, i, target, s, 0, n, res);
            else {
                //num: 넘기고
                //start+i: +,-,*공용으로 시작위치 옮기고 
                //target: 넘기고
                //path: str을 완성해준다. 이전까지 완성한 식에 연산자 char 붙여주고, 현재 뽑은 str도 뒤이어 붙여준다
                //prev: + - 는 이전값에 현재값을 더해주고, 이번 loop에서 뽑은 값을 cur로 넘겨주면 된다.
                //*의 경우에는 prev는 냅두고, 현재값과 이번 loop에서 뽑은 값을 곱해주고 넘긴다.
                //사실 이번 loop가 n회차라면 prev는 n-2회차, cur는 n-1회차, n은 n회차 라고 생각해야 할듯 싶다.
                dfs(num, start + i, target, path + "+" + s, prev + cur, n, res);
                dfs(num, start + i, target, path + "-" + s, prev + cur, -n, res);
                dfs(num, start + i, target, path + "*" + s, prev, cur * n, res);
            }
        }
    }
};