프로그래머스 - 수식 최대화(2020 카카오 인턴십)

처음 떠올린 방법은 스택을 사용하지 않는 방법이었다. 

string을 *+-로 해두고 3!의 경우에 대해서 모두 계산해보는 방법을 사용했는데, 처음에 *를 expression에서 다 찾아서 계산하고, +, - 순으로 계산하는 방법을 생각했다. 

이 때, vector의 값을 어떻게 변화시켜야 하는지가 바로 떠오르지 않아 다른 방법으로 풀려고 했던 것 같다. 

 

아래는 스택을 사용한 방법인데, 각 연산자의 우선순위를 확인하여 우선순위가 높은 연산자를 먼저 수행하게끔 스택을 관리하면서 값을 계산하면 된다. (즉, 스택에 있는 연산자가 다음 연산자보다 우선순위가 높다면 바로 수행 아니면 스택에 쌓아놓는다.)

 

코드 - 스택을 사용한 방법

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
map<char, int> prio;
long long cal(long long a, char op, 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> num;
    vector<char> op;
    string tmp = "";
    for(int i=0; i<expression.size(); i++)
    {
        if (expression[i] == '-' || expression[i] == '+' || expression[i] == '*')
        {
            op.push_back(expression[i]);
            num.push_back(stoi(tmp));
            tmp = "";
        }
        else
            tmp += expression[i];
    }
    num.push_back(stoi(tmp));
    string s = "*+-";
    int n_len = num.size();
    int op_len = op.size();
    do{
        for(int i=0; i<s.size(); i++)
            prio[s[i]] = i; //숫자가 작은게 우선순위가 크다.
        stack<long long> num_stack;
        stack<char> op_stack;
        num_stack.push(num[0]);
        int idx = 0;
        for(int i=1; i<n_len; i++)
        {
            num_stack.push(num[i]);
            op_stack.push(op[idx]);
            idx++;
            if (prio[op_stack.top()] <= prio[op[idx]])
            {
                while (!op_stack.empty())
                {
                    if (prio[op_stack.top()] <= prio[op[idx]])
                    {
                        long long two = num_stack.top(); num_stack.pop();
                        long long one = num_stack.top(); num_stack.pop();
                        char oper = op_stack.top(); op_stack.pop();
                        num_stack.push(cal(one, oper, two));
                    }
                    else break;
                }
            }
        }
        while (!op_stack.empty())
        {
            long long two = num_stack.top(); num_stack.pop();
            long long one = num_stack.top(); num_stack.pop();
            char oper = op_stack.top(); op_stack.pop();
            num_stack.push(cal(one, oper, two));
        }
        answer = max(answer, abs(num_stack.top()));
        num_stack.pop();
    }while (next_permutation(s.begin(), s.end()));
    return answer;
}

핵심은 while()문을 이용해서 op_stack이 빌 때 까지 계산해줘야 한다는 점이다. 만약 다음 연산자보다 우선순위가 더 높다면 모두 꺼내서 계산한다. 그게 아니면 break해주어야 한다.

 

코드 - 스택을 사용하지 않은 방법

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
map<char, int> prio;
long long cal(long long a, char op, 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> num;
    vector<char> op;
    string tmp = "";
    for(int i=0; i<expression.size(); i++)
    {
        if (expression[i] == '-' || expression[i] == '+' || expression[i] == '*')
        {
            op.push_back(expression[i]);
            num.push_back(stoi(tmp));
            tmp = "";
        }
        else
            tmp += expression[i];
    }
    num.push_back(stoi(tmp));
    string s = "*+-";
    int n_len = num.size();
    int op_len = op.size();
    do{
        vector<long long> t_num = num;
        vector<char> t_op = op;
        for(int i=0; i<s.size(); i++)
        {
            for(int j=0; j<t_op.size(); j++)
            {
                if (t_op[j] == s[i])
                {
                    long long res = cal(t_num[j], t_op[j], t_num[j + 1]);
                    t_num[j] = res;
                    t_num.erase(t_num.begin() + j + 1);
                    t_op.erase(t_op.begin() + j);
                    j--;
                }
            }
        }
        answer = max(answer, abs(t_num[0]));
    }while (next_permutation(s.begin(), s.end()));
    return answer;
}

계산을 하고 t_num[j]에다가 결과값을 저장한 다음 t_num[j + 1]을 erase해버리면 되었다. 연산자도 하나 사용했기 때문에 t_op[j]를 erase한다. 

항상 vector를 erase했을 때는 배열의 index를 잘 관리해주어야 하는데, vector의 원소가 하나 줄었기 때문에 j--를 통해 지우기 전의 문자부터 볼 수 있도록 계산해준다.