프로그래머스 - 수식 최대화 - Level 2

문제

풀이전략

1. 이 문제는 연산자의 우선순위를 자유롭게 재 정의하여 가장 최대값이 나오도록 문제를 해결해야한다.
2. 주어진 수식에서 숫자와 연산자를 따로 추출해야한다.
3. next_permutation함수를 사용하여 해결한다.

코드

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

using namespace std;

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

long long solution(string expression){
    long long answer = 0;
    
    vector<long long> record_operand;
    vector<char> record_operator;
    string temp = "";
    for(int i=0; i<expression.length(); i++){
        if(expression[i] >= '0' && expression[i] <= '9') temp += expression[i];
        else{
            record_operator.push_back(expression[i]);
            // string을 longlong으로 바꿔주는 stoll함수
            record_operand.push_back(stoll(temp));
            temp = "";
        }
    }
    record_operand.push_back(stoll(temp));
    
    vector<int> perm = {0, 1, 2};
    string op = "+-*";
    do{
        vector<long long> temp_operand = record_operand;
        vector<char> temp_operator = record_operator;
        
        for(int i=0; i<perm.size(); i++){
            for(int j=0; j<temp_operator.size();){
                if(temp_operator[j] == op[perm[i]]){
                    // j번째의 operator는 사실상 j번째 수와 j+1번째 수의 op 이기 때문에
                    long long res = calculate(temp_operand[j], temp_operand[j+1], temp_operator[j]);
                    
                    // j번째 수를 사용하였으니 그 수를 제거함
                    temp_operand.erase(temp_operand.begin()+j);
                    // j번째수를 제거하면 j+1번째 수가 j번째 수가 되고 이또한 제거해야하므로 한번 더 반복
                    temp_operand.erase(temp_operand.begin()+j);
                    // 합한 수를 다시 넣어주기
                    temp_operand.insert(temp_operand.begin()+j,res);
                    // 사용한 operator삭제
                    temp_operator.erase(temp_operator.begin()+j);
                }
                else j++;
            }
        }
        answer = max(answer, abs(temp_operand[0]));
        // 순열을 사용하기!!
    }while(next_permutation(perm.begin(), perm.end()));
    return answer;
}

소감

나는 해결하지 못하여 다른 분의 풀이를 보고 공부하였다. 먼저 문자열과 연산자만 추출하는 부분을 보고 배웠다. 또한 next_permutation을 처음에는 어떻게 사용하는지 몰랐는데 이제 어떻게 사용해야하는지 확실히 알게되었다..... 더 집중해서 열심히하겠씁니다.