[프로그래머스/C++] 수식 최대화

 

프로그래머스

 

 

 

• 연산자의 우선순위를 임의로 정하여 입력받은 식의 값의 절댓값 중 가장 큰 값을 구해야함
• 연산자의 우선순위는 중복 불가
• 주어지는 연산자는 +, -, *

 

> 연산자 간의 순열을 이용, 주어지는 연산자가 3개뿐이므로 순열은 총 3!가지

> + > - > * 순서가 될 시 +를 먼저 계산 후 -, * 순서로 계산하도록 반복하면 됨

> 연산 후 피연산자 2개를 삭제 후 결과를 해당 위치에 삽입하고, 연산자의 삭제도 필요

 

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

using namespace std;

long long calc(char op, long long a, long long b) {
    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> operands;
    // 연산자 벡터
    vector<char> operators;
    string tmp;
    
    // 연산자와 피연산자를 분리
    for(int i = 0; i < expression.size(); i++) {
        if(expression[i] >= '0' && expression[i] <= '9')
            tmp += expression[i];
        else {
            operators.push_back(expression[i]);
            operands.push_back(stoll(tmp));
            tmp = "";
        }
    }
    
    operands.push_back(stoll(tmp));
    
    // 주어진 연산자
    string oper = "*+-";
    
    do {
    	//연산자와 피연산자 배열 복사
        vector<long long> operandTmp = operands;
        vector<char> operatorTmp = operators;
        
        // 연산자 수만큼 반복
        for(int i = 0; i < 3; i++) {
        	// 연산자 배열 크기만큼 반복
            for(int j = 0; j < operatorTmp.size();) {
                if(operatorTmp[j] == oper[i]) {
                    long long tmp = calc(operatorTmp[j], operandTmp[j], operandTmp[j + 1]);
                    
                    // 피연산자 2개를 지움
                    operandTmp.erase(operandTmp.begin() + j);
                    operandTmp.erase(operandTmp.begin() + j);
                    // 해당 위치에 결과값 삽입
                    operandTmp.insert(operandTmp.begin() + j, tmp);
                    
                    // 사용한 연산자를 지움
                    operatorTmp.erase(operatorTmp.begin() + j);
                }
                else
                    j++;
            }
        }
        
        // 절댓값이 가장 큰 경우 찾기
        answer = max(answer, abs(operandTmp[0]));
    } while (next_permutation(oper.begin(), oper.end())); // 순열
    
    return answer;
}

 

> 계속 5번이 틀려서 질문 목록을 보니 문자열 순서가 *+-되어야한다는 글이 있어서 바꿔보니 해결되었다.

> 왜 그런지에 대한 답변은 어디에도 없었다....