[2020 카카오 인턴] 수식 최대화 (C++)

2020 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - 수식 최대화 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 수식 최대화

---

2번 문제였으며 약 1시간 정도 소요되었다.

dfs를 써서 각 우선순위의 연산자 순서대로 배열에 넣으며 계산한다.

어렵지는 않았으나 바로 생각이 안났었다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

vector<long long> num;
vector<char> operand_pred;
map<int, char> temp;
bool visited[3] = { false };
string operand_list = "";
int cnt = 0;
long long ans = 0;

long long calculate(long long a, long long b, char op)
{
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
}

long long calculate_all()
{
    vector<long long> cal = num;
    string op_list = operand_list;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < op_list.size(); j++)
        {
            if (op_list[j] == operand_pred[i])
            {
                long long res = calculate(cal[j], cal[j + 1], op_list[j]);
                cal.erase(cal.begin() + j);
                cal[j] = res;
                op_list.erase(op_list.begin() + j);
                j--;
            }
        }
    }

    return abs(cal[0]);
}

void DFS(int ind)
{
    if (ind == 3)
    {
        long long res = calculate_all();
        ans = max(res, ans);
        return;
    }

    for (int i = 0; i < 3; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            operand_pred.push_back(temp[i]);
            DFS(ind + 1);
            operand_pred.pop_back();
            visited[i] = false;
        }
    }
}

long long solution(string expression) {
    long long answer = 0;
    temp[0] = '+';
    temp[1] = '-';
    temp[2] = '*';

    string n = "";
    for (int i = 0; i < expression.size(); i++)
    {
        if (!isdigit(expression[i]))
        {
            num.push_back(stoll(n));
            n = "";
            operand_list += expression[i];
        }
        else
            n += expression[i];
    }
    num.push_back(stoll(n));

    DFS(0);

    answer = ans;
    return answer;
}