수식 최대화

코드

#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()));

    /* expression을 숫자와 기호로 나누기 */
    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()을 사용하면 이 전 조합으로도 갈 수 있음!