Level 2. 수식 최대화

Level 2. 수식 최대화

 

 

우선 숫자들과 연산자들을 분리했다.

• 문자를 하나씩 읽으면서 숫자면 기존 숫자에 10을 곱한 후 더하고, 문자면 연산자로 취급했다.

 

이후 +, -, * 세 가지 연산자의 우선순위인 6가지 경우의 수에 대해 직접 계산해 해결했다.

• 우선순위가 높은 순으로 앞에서부터 검색하며 해당 연산자가 있으면 계산하면 된다.
• a ￮ b의 계산은 a 위치에 a ￮ b의 결괏값을 저장하고 숫자 b와 연산자 ￮를 제거하는 식으로 진행했다.
• 계산을 마치면 숫자 vector에는 최종 결괏값 1개만 남게 된다.

 

#include <iostream>
#include <vector>
#include <cctype>
#include <algorithm>

using namespace std;

long long calculate(long long A, long long B, char op)
{
    switch (op)
    {
    case '+': return A + B;
    case '-': return A - B;
    case '*': return A * B;
    default:  return 0;
    }
}

long long solution(string expression)
{
    long long answer = 0;

    vector<long long> nums;
    vector<char> ops;
    bool isNumberTurn = true;

    for (char c : expression)
    {
        if (isNumberTurn)
            nums.emplace_back(0),
            isNumberTurn = false;

        if (isdigit(c))
            nums.back() *= 10,
            nums.back() += c - '0';
        else
            ops.emplace_back(c),
            isNumberTurn = true;
    }

    vector<string> cases {"-+*", "-*+", "+-*", "+*-", "*+-", "*-+"};

    for (string& cs : cases)
    {
        vector<long long> t_nums = nums;
        vector<char> t_ops = ops;

        for (char op : cs)
        {
            for (int i = 0; i < t_ops.size(); ++i)
            {
                if (t_ops[i] == op)
                {
                    t_nums[i] = calculate(t_nums[i], t_nums[i + 1], op);

                    t_nums.erase(t_nums.begin() + i + 1);
                    t_ops.erase(t_ops.begin() + i--);
                }
            }
        }

        answer = max(answer, abs(t_nums[0]));
    }

    return answer;
}