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

수식 최대화

문제)

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

풀이)

next_permutation으로 연산자의 우선순위를 바꿔주면서 푼 문제이다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cardi[3];// + - *
long long solution(string expression) {
    long long answer = 0;
    vector <long long> number;
    vector <int> oper;
    string s;
    for (int i = 0; i < expression.length(); i++) {
        char ch = expression[i];
        if (ch == '+') {
            cardi[0] = true;
            oper.push_back(0);
            number.push_back(stoi(s));
            s = "";
        }
        else if (ch == '-') {
            cardi[1] = true;
            oper.push_back(1);
            number.push_back(stoi(s));
            s = "";
        }
        else if (ch == '*') {
            cardi[2] = true;
            oper.push_back(2);
            number.push_back(stoi(s));
            s = "";
        }
        else s += ch;
    }
    number.push_back(stoi(s));
    vector <int> priority;
    for (int i = 0; i < 3; i++) {
        if (cardi[i]) {
            priority.push_back(i);
        }
    }
    do {
        vector <long long> t_number = number;
        vector <int> t_oper = oper;
        long long temp;
        for (int i = 0; i < priority.size(); i++) {
            int o = priority[i];
            for (int j = 0; j < t_oper.size(); j++) {

                if (t_oper[j] == o) {

                    if (o == 0) {//+
                        t_number[j] = t_number[j] + t_number[j + 1];
                    }
                    else if (o == 1) {//-
                        t_number[j] = t_number[j] - t_number[j + 1];
                    }
                    else {//*
                        t_number[j] = t_number[j] * t_number[j + 1];
                    }
 t_number.erase(t_number.begin() + j + 1);
                    t_oper.erase(t_oper.begin() + j--);//j 줄여줌. 연산자 개수 하나줄었으므로
                }
            }

        }
        if (t_number[0] < 0) t_number[0] *= -1;
        if (answer < t_number[0]) answer = t_number[0];
    } while (next_permutation(priority.begin(), priority.end()));
    return answer;
}

+ 숫자와 연산자 저장할 때 substr을 이용한 간단한 방법

    int idx = 0;
    for(int i=0;i<expression.length();i++){
        char ch = expression[i];
        if(ch == '*' | ch == '+' | ch == '-'){
            oper.push_back(ch);
            number.push_back(stoi(expression.substr(idx,i-idx)));
            idx = i+1;
        }else if(i == expression.size()-1){
            number.push_back(stoi(expression.substr(idx,i-idx+1)));
        }
    }

+ next_permutation을 사용하지 말고 그냥 연산자 우선순위를 따로 저장해서 사용하는 방법(연산자 3개를 default로 둔다)

 string prior[6] = {
        "*+-", "*-+",
        "+*-", "+-*", 
        "-*+", "-+*",
    };