일련의 숫자와 연산자가 있다고 가정하고 숫자와 연산자를 그룹화하기 위해 가능한 모든 방법을 계산하여 가능한 모든 결과를 찾아야 합니다. 여기서 유효한 연산자는 +, - 및 *입니다. 따라서 입력이 "2*3-4*5"와 같으면 출력은 [-34, -14, -10, -10, 10]이 됩니다. 그 이유는 -
-
(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
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
메모라는 지도를 정의합니다.
-
solve()라는 메서드를 정의합니다. 이것은 입력 문자열을 입력으로 받습니다.
-
ret
라는 배열을 만듭니다. -
메모에 입력이 있으면 메모를 반환합니다[입력]
-
범위 0에서 입력 문자열의 크기까지 i의 경우 -
-
input[i]가 지원되는 연산자인 경우
-
배열 part1 :=solve(0에서 i - 1까지의 입력 부분 문자열)
-
배열 part2 :=solve(i에서 문자열 끝까지 입력의 부분 문자열)
-
범위 0에서 part1의 크기에 있는 j의 경우
-
범위 0에서 part2의 크기까지 k의 경우
-
input[i]가 덧셈이면
-
part[j] + part[k]를 수행하고 ret에 추가
-
-
input[i]가 곱셈이면
-
part[j] * part[k]를 수행하고 ret에 추가
-
-
input[i]가 빼기이면
-
part[j] - part[k]를 수행하고 ret에 추가
-
-
-
-
-
-
ret가 비어 있으면 입력 문자열을 정수로 반환
-
메모[입력] :=ret, 반환 ret
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
map <string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector <int> ret;
if(memo.count(input)) return memo[input];
for(int i = 0; i < input.size(); i++){
if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
vector <int> part1 = diffWaysToCompute(input.substr(0, i));
vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
for(int j = 0; j < part1.size(); j++ ){
for(int k = 0; k < part2.size(); k++){
if(input[i] == '+'){
ret.push_back(part1[j] + part2[k]);
}
else if(input[i] == '*'){
ret.push_back(part1[j] * part2[k]);
} else {
ret.push_back(part1[j] - part2[k]);
}
}
}
}
}
if(ret.empty()){
ret.push_back(stoi(input));
}
return memo[input] = ret;
}
};
main(){
Solution ob;
print_vector(ob.diffWaysToCompute("2*3-4*5"));
} 입력
"2*3-4*5"
출력
[-34, -10, -14, -10, 10, ]