[Level_2 / C++ / 카카오] 수식 최대화

<erase/insert> 삭제 및 삽입

<next_permutation> 모든 경우의 수 정렬

---

우선 연산자의 우선순위가 주어지는데 총 세가지 연산자가 있다. 

"*", "-", "+"

이 연산자를 p_cal 이라는 벡터에 넣고 정렬해준다. 

next_permutaion 함수를 적용하기 위해서는 아스키코드가 작은값부터 정렬이 되어야 모든 경우의 수를 정렬할 수 있기 때문이다. 

 

정렬 됐으면 첫번째 우선순위의 연산자를 계속 수행하는것이다. 

 

즉, 첫번째 우선순위 연산자는 (*) -> (+) -> (-) 이런순으로 되어있는데, 먼저 * 연산자에 해당되는 인덱스 

전 후의 값들을 * 연산을 다 해준다. 이후 +와 - 연산자 또한 다음과 같이 수행한다. 

그리고 그 값의 절댓값이 가장 큰 값을 저장시켜준다. 

 

두번째 우선순위 연산자는 next_permutation 함수를 통해 

 (*) -> (-)  -> (+) 가 나온다. 이 순서대로 연산을 해준다. 

 

연산자는 총 3개이니 3X2X1 = 6 가지의 우선순위로 정렬된 연산자들을 통해 값을 도출한다. 

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll cal_act(ll a, ll b, char c) {
    if (c == '-')return a - b;
    else if (c == '*')return a * b;
    else return a + b;
}
long long solution(string expression) {
    string s = expression;
    long long answer = 0;
    vector <char> p_cal = { '*','+','-' };
    vector <ll> num;
    vector <char> cal;
    sort(p_cal.begin(), p_cal.end());
    string temp = "";
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9')temp += s[i];
        else {
            num.push_back(stoll(temp));
            cal.push_back(s[i]);
            temp = "";
        }
    }
    num.push_back(stoll(temp));
    ll max_num = -1;
    do {
        vector <ll>n = num;
        vector <char> c = cal;       
        for (int i = 0; i <= 2; i++) {
            for (int j = 0; j < c.size(); ) {
                if (p_cal[i] == c[j]) {              
                    ll result = cal_act(n[j], n[j + 1], c[j]);
                    n.erase(n.begin() + j, n.begin()+j+2);           
                    c.erase(c.begin() + j);
                    n.insert(n.begin() + j, result);            
                }
                else j++;                 
            }            
        }
        max_num = max(max_num, abs(n[0]));
    } while (next_permutation(p_cal.begin(), p_cal.end()));
    return max_num;
}

코딩테스트 연습 - 수식 최대화