[LeetCode] 24-game

https://leetcode.com/problems/24-game/

[1.문제이해]

숫자 4개가 주어지고 (*,+,/,-)연산자와 (,)를 모두 써서 숫자 24를 만들 수 있는지가 문제였다.
일단 숫자는 정렬조건은 주어지지 않고 자유롭게 배치할 수 있다.

[2.문제접근]

일단 숫자 4개에 관해서 순서를 배치하는데 걸리는 계산복잡도는 4!이다.
이때 여러가지 연산자를 사용할 수 있는데 이때, (,)까지 생각하여야 하는 문제다.
즉 순서대로 연산이 일어나는게 아니라 먼저 계산할것끼리 묶어주는 작업이 필요하다.
처음에 생각한 방식은 다음과 같다. op는 { + - * / }중 하나이다.

//방식 1:
void calculate(nums,index,cur):
if(index==4 and cur== 24) "정답"
calculate (nums,index+1,cur (op) nums[index])
//방식 2:
int calculate(nums,index,cur):
result= calculate (nums,4,cur (op) calcultate(nums,index+1,nums[index]))
return result;

방식 1의 경우는 현재 연산한 결과를 Parameter로 넘겨주는 방식이다.
방식 1로 할경우 다음과 같은 연산을 불가하다 . A+(B*C);

방식 2의 경우는 연산한 결과를 return하는 방식이다.
방식 2의 경우는 A+(B*C)와 같은 연산이 가능하다. 하지만 함수내에서 return 이 필요하며 반환하는 값은 한개만 받을 수 있으므로 다음과 같은 문제가 생긴다.

result= calcultate(nums,index+1,cur+nums[index]))
result= calcultate(nums,index+1,cur*nums[index]))
result= calcultate(nums,index+1,cur-nums[index]))
result= calcultate(nums,index+1,cur/nums[index]))
return result;

물론 인자를 List와 같은 컨테이너로 받으면 되지만 복잡성이 증대한다.

[3.해결]

숫자가 A,B,C,D와 같이 주어질때 A+B+(C*D)와 같은 작업을 하기 위해서 다음과 같이 접근한다.
매번 조합을 진행하여 남은 피연산자들을 조합해서 연산작업을 진행한다.
A+B=AB라고 하고 다음 시나리오를 보자

1.. nums=[A,B,C,D] //초기 nums
2.. tmp=[] //빈컨테이너
3.. tmp.push(AB) //숫자 2개를 선택(NC2)하여 연산(4) => 4 * Nc2
4.. tmp.push(C,D) //선택되지 않은것들을 컨테이너에 담음
5.. tmp=[C,D,AB] //결과
6.. nums=tmp //다시 1->5방법하여 길이가 1될때 까지 진행
.
...
와 같은 작업을 할시 다음과 같이 중간 괄호의 문제를 해결 할 수있다.

[4.코드]

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> tmp(nums.begin(), nums.end());
        return dfs(tmp);
    }
private:
    bool dfs(vector<double>& nums){
        if(nums.size() == 1) return fabs(nums[0] - 24) < 1e-8;
        for(int i = 0; i + 1 < nums.size(); ++i){
            for(int j = i + 1; j < nums.size(); ++j){
                vector<double> tmp;
                for(int k = 0; k < nums.size(); ++k)
                    if(k != i && k != j) tmp.push_back(nums[k]);
                tmp.push_back(nums[i] + nums[j]);
                if(dfs(tmp)) return true;
                tmp.back() = nums[i] * nums[j];
                if(dfs(tmp)) return true;
                tmp.back() = nums[i] - nums[j];
                if(dfs(tmp)) return true;
                tmp.back() = nums[i] / nums[j];
                if(dfs(tmp)) return true;
                tmp.back() = nums[j] - nums[i];
                if(dfs(tmp)) return true;
                tmp.back() = nums[j] / nums[i];
                if(dfs(tmp)) return true;
            }
        }
        return false;
    }
};