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

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

using namespace std;

long long cal(long long a, long long b, char op)
{
    if(op == '+' ) return a+b;
    else if(op == '-') return a-b;
    else return a*b;
}

long long solution(string expression) {
    long long answer = 0;
    vector<char>v = {'*', '+', '-'};
    vector<long long>num;
    vector<char>op;
    
    string tmp = "";
    for(int i=0; i<expression.size(); i++)
    {
        if(expression[i] >= '0' && expression[i] <='9') tmp += expression[i]; //숫자 분리
        else
        {
            num.push_back(stoll(tmp)); //숫자 저장 후 초기화
            tmp = "";
            op.push_back(expression[i]); //연산자 저장
        }
    }
    num.push_back(stoll(tmp)); //마지막 숫자 저장
    
    do
    {
        //다른 우선 순위 조합을 위해 복사한 값 사용
        vector<long long> num2 = num;
        vector<char> op2 = op;
        for(int i=0; i<3; i++) // 3개의 연산자 
        {
            for(int j=0; j<op2.size();) //연산 수행
            {
                if(v[i]==op2[j]) //우선순위에 따른 연산 모두 수행
                {
                    long long result = cal(num2[j], num2[j+1], op2[j]); 
                    num2.erase(num2.begin() + j, num2.begin() + j + 2); //연산한 숫자 삭제
                    num2.insert(num2.begin() + j, result); //연산 결과 삽입
                    op2.erase(op2.begin() + j); //사용한 연산자 삭제
                }
                else j++;
            }
        }
        answer = max(answer, abs(num2[0]));
    }while(next_permutation(v.begin(), v.end()));
    return answer;
}

 

입력받은 문자열을 숫자와 연산자로 나눠서 저장부터 해준다.

우선순위 문자열을 기준으로 연산 수행을 하게 되는데, 이때 next_permutation 함수를 통해 연산자 우선순위를 바꿔주며 최대값을 찾게 된다.

해당 함수는 사용을 위해 미리 해당 벡터를 정렬해줘야 하는데, 해당 벡터의 값이 3개 밖에 안되므로 미리 아스키 값에 따라 정렬해서 선언해주면 굳이 정렬 함수를 사용해 정렬해줄 필요가 없어진다.

 

이제 우선순위에 따른 연산을 수행하는데, 현재 연산자에 따라 계산을 진행한다.

연산한 숫자는 이제 다른 연산결과로 합쳐졌으니 기존 연산한 숫자와 연산자를 삭제해주고, 연산 결과를 삽입해준다.

이를 우선순위 3개의 연산자와 연산자 크기 만큼 반복해서 계산하게 된다.

이때 다음 조합을 위해 기존 원본은 저장해야 하므로, 연산 결과 삭제 및 삽입은 복사본을 통해 이루어져야 한다.