Programmers : 수식 최대화

문제링크

풀이 요약

구현

풀이 상세

1. 연산자 3가지를 통해 나올 수 있는 모든 경우의 수는 6가지이므로 먼저 우선순위를 나타내는 연산자 배열을 생성한다.

2. expression 를 통해 연산자로 나뉘어진 백터를 생성한다.

3. 연산자 배열과 expression 백터를 통해, 우선순위에 맞게 계산한다. 계산이 반복되지 않도록, 계산이 완료된 항목을 백터에서 제거한다.

4. 6가지 연산 순서에 따른 최종값을 절댓값으로 치환하여 이전까지의 최댓값도 비교한다.

#include <string>
#include <vector>
using namespace std;
string comp[6][3] = {{"+", "-", "*"},
                     {"+", "*", "-"},
                     {"*", "-", "+"},
                     {"*", "+", "-"},
                     {"-", "+", "*"},
                     {"-", "*", "+"}};

vector<string> split(string str) {
    vector<string> temp;
    string tmp = "", s = "";
    int idx = -1;
    while (++idx < str.size()) {
        if (str[idx] == '+' || str[idx] == '-' || str[idx] == '*') {
            temp.push_back(tmp);
            tmp = "";
            temp.push_back(s += str[idx]);
            s = "";
        } else tmp += str[idx];
    }
    temp.push_back(tmp);
    return temp;
}

long long calc(string s1, string s2, string op) {
    if (op == "+")
        return stoll(s1) + stoll(s2);
    else if (op == "-")
        return stoll(s1) - stoll(s2);
    else
        return stoll(s1) * stoll(s2);
}

long long solution(string expression) {
    long long answer = 0;
    // 문자열 스플릿 (+, -, *);
    vector<string> s = split(expression);

    for (int i = 0; i < 6; i++) {
        vector<string> ss(s);
        for (int j = 0; j < 3; j++) {
            int len = ss.size();
            for (int k = 1; k < len; k += 2) {
                if (ss[k] == comp[i][j]) {
                    ss[k] = to_string(calc(ss[k - 1], ss[k + 1], ss[k]));
                    ss.erase(ss.begin() + k + 1);
                    ss.erase(ss.begin() + k - 1);
                    k -= 2;
                }
            }
        }
        answer = max(answer, abs(stoll(ss[0])));
    }
    return answer;
}