[프로그래머스] level2 수식 최대화 (C++)

풀이

1. 주어진 표현식을 숫자와 연산자로 나눈 후 각각 다른 배열에 넣어준다.
2. 기본적인 백트래킹을 사용해 '*+-'로 구성된 연산자의 순서를 정해준다.
3. 백트래킹의 마지막 부분에 도달해 연산자의 순서가 정해지면 표현식을 순서대로 계산한다.
   • 현재 표현식의 연산자(forj)와 우선순위에 따른 연산자(fori)가 동일한 경우에 값을 계산해서 적절한 위치에 값을 갱신해준다.
     그리고 사용한 연산자와 숫자는 erase메서드를 사용해서 지워준다.
   • 여기서 주의할 점은 벡터를 for문으로 순회하는 도중에 원소가 지워지면 인덱스에 문제가 생길 수 있다.
     따라서 현재 인덱스를 지워진 원소의 개수만큼 빼줘야 한다.
4. 계산된 값을 비교하면서 최댓값을 저장해둔다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

// *, -, + 
string ex = "*-+";
bool visited[3];
vector<ll> nums;
vector<char> exps;
ll answer = 0;

ll calc(ll a, ll b, char nowexp){
    if(nowexp == '*') return a*b;
    if(nowexp == '-') return a-b;
    if(nowexp == '+') return a+b;
}

ll solve(string order){
    vector<ll> newnums = nums;
    vector<char> newexps = exps;
    
    for(int i = 0; i < 3; i++){
        char nowexp = order[i];
        for(int j = 0; j < newexps.size(); j++){
            if(newexps[j] == nowexp){
                ll temp = calc(newnums[j], newnums[j+1], newexps[j]);
                newnums[j] = temp;
                newnums.erase(newnums.begin() + j + 1);
                newexps.erase(newexps.begin() + j);
                j--;
            }
        }
    }
    
    return abs(newnums[0]);
}

void backtracking(int cnt, string order){
    if(cnt == 3){
        answer = max(answer, solve(order));
        return;
    }
    
    for(int i = 0; i < 3; i++){
        if(visited[i]) continue;
        visited[i] = true;
        backtracking(cnt+1, order + ex[i]);
        visited[i] = false;
    }
}

ll solution(string expression) {
    
    ll t = 0;
    for(int i = 0; i < expression.size(); i++){
        if(expression[i] == '*' || expression[i] == '+' || expression[i] == '-'){
            nums.push_back(t);
            exps.push_back(expression[i]);
            t = 0;
        }
        else t = 10 * t + (expression[i] - '0');
    }
    nums.push_back(t);
    
    // 백트래킹으로 우선순위 정하기
    backtracking(0, "");
    
    return answer;
}