[프로그래머스][Level2] 수식 최대화 c++

https://programmers.co.kr/learn/courses/30/lessons/67257 

 

풀이 과정

연산이 string 자료형으로 주어졌기 때문에, 반복문을 돌려  
num 벡터에 숫자를 담고, op 벡터에 연산자를 담는다.

그리고 3가지 연산문자를 준비해 순열 알고리즘을 쓴다.  
그 이유는 우선순위를 정하기 위해서다.

처음에는 *, +, - 순으로 우선순위가 정해져 계산을 하는데,  
계산을 하는 도중에 원래 벡터들을 삭제하는 과정이 있기 때문에  
num벡터와 op벡터를 순열이 시작될 때마다 temp 벡터로 만들어줘야한다.

- 새로 알게된 점!
  max를 쓰려면 두 자료형이 맞아야 한다.  
  예를 들어 max(int, long long)이면 안 되고, max(long long, long long)이여야만 한다!

 

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

using namespace std;

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

long long solution(string expression) {
    long long answer = 0;
    vector<long long> num; // 숫자
    vector<char> op; // 연산자

    string temp = "";
    for(int i = 0; i < expression.size(); i++){
        if('0' <= expression[i] && expression[i] <= '9'){
            temp += expression[i];
        }
        else{
            num.push_back(stoll(temp));
            op.push_back(expression[i]);
            temp = "";
        }
    }
    if(temp != "") num.push_back(stoll(temp));

    char oplist[3] = {'+', '-', '*'};
    sort(oplist, oplist + 3);

    do{
        vector<long long> num_temp = num;
        vector<char> op_temp = op;
        for(int i = 0; i < 3; i++){ // oplist
            for(int j = 0; j < op_temp.size(); j++){ // 실제 연산자
                if(oplist[i] == op_temp[j]){
                    num_temp[j] = calc(num_temp[j], num_temp[j + 1], op_temp[j]);
                    num_temp.erase(num_temp.begin() + j + 1);
                    op_temp.erase(op_temp.begin() + j);
                    j--;
                }
            }
        }
        answer = max(answer, abs(num_temp[0]));
    }while(next_permutation(oplist, oplist + 3));

    return answer;
}