#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cmath>
using namespace std;
long long solution(string expression) {
long long answer = 0;
int arr[3] = {'+','-','*'};
vector<char> ch;
for(int i=0;i<3;i++) {
auto it = find(expression.begin(), expression.end(), arr[i]);
if(it != expression.end()) ch.push_back(arr[i]);
}
int untill = 1;
for(int i=ch.size();i>=1;i--) untill*=i;
vector<int> tmp(ch.size());
vector<vector<string>> v(untill);
for(int i=0;i<tmp.size();i++) tmp[i] = i;
int q=0;
do{
for(int i=0;i<tmp.size();i++){
string t ="";
t += ch[tmp[i]];
v[q].push_back(t);
}
q++;
}while(next_permutation(tmp.begin(), tmp.end()));
stringstream ss(expression);
vector<string> s;
int n;char c;
while(true)
{
ss >> n;
s.push_back(to_string(n));
if(ss.eof()) break;
ss >> c;
string t="";
t+=c;
s.push_back(t);
}
long long MAX = 0;
for(int i=0;i<v.size();i++)
{
vector<string> temp(s);
for(int j=0;j<v[i].size();j++)
{
for(int z=0;z<temp.size();z++)
{
if(temp[z] == v[i][j]){
long long n1 = stoll(temp[z-1]);
long long n2 = stoll(temp[z+1]);
long long result;
if(v[i][j] == "+") result = n1+n2;
else if(v[i][j] == "-") result = n1-n2;
else if(v[i][j] == "*") result = n1*n2;
temp.erase(temp.begin()+z+1);
temp.erase(temp.begin()+z);
temp[z-1] = to_string(result);
z -=2;
}
}
}
MAX = max(MAX,abs(stoll(temp.front())));
}
answer = MAX;
return answer;
}
- key point!
: 연산자의 종류 개수에 따라 가능한 조합을 구하는 것이 관건
<algorithm>
에 next_permutation()
을 이용하면 현재 조합에서 다음 순열을 구할 수 있음!
vector<int> tmp(ch.size());
vector<vector<string>> v(untill);
for(int i=0;i<tmp.size();i++) tmp[i] = i;
int q=0;
do{
for(int i=0;i<tmp.size();i++){
string t ="";
t += ch[tmp[i]];
v[q].push_back(t);
}
q++;
}while(next_permutation(tmp.begin(), tmp.end()));
- tmp배열에 [0, 1, 2, 3, 4] 가 있을 때
[0,1,2,3,4] ~ [4,3,2,1,0] 까지 모든 조합으로 바꾸어 준다
- 반환형은
bool
형이기 때문에 조건으로 사용!
prev_permutation()
을 사용하면 이 전 조합으로도 갈 수 있음!