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

 이 문제는 프로그래머스 Level 2 문제이다. 이 문제는 구현이 어려운 편에 속하고, 백트래킹을 이용해 연산자 우선순위를 정하고, long long 자료형을 사용해야 한다는 사실을 캐치하면 풀 수 있다.

 

 수식이 정해져 있고, 연산자 우선순위가 같은 경우가 없기 때문에 다이나믹 프로그래밍을 생각해내기 어려웠다. 연산자가 최대 3개이므로 우선순위 경우의 수는 최대 6이다. 따라서 O(N) 시간의 알고리즘으로도 1초 안에 풀 수 있다. 연산하는 것까지 구현을 잘 했지만, long long 자료형을 사용해야 한다는 점을 파악하지 못해 처음에 오답이 나왔다. 그러나 문제를 다시 읽고 바로 수정한 뒤 정답을 받을 수 있었다.

 

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

using namespace std;

vector<char> used;

long long solve(vector<int> temp, vector<bool> tempUsed, vector<long long> numbers, vector<char> opers) {
    if (temp.size() == used.size()) {
        for (int i = 0; i < temp.size(); i++) {
            char oper = used[temp[i]];
            
            if (oper == '*') {
                long long first = numbers[0];
                vector<long long> tempNum;
                vector<char> tempOper;
                
                for (int j = 1; j < numbers.size(); j++) {
                    long long second = numbers[j];
                    
                    if (opers[j - 1] != oper) {
                        tempOper.push_back(opers[j - 1]);
                        tempNum.push_back(first);
                        first = second;
                    }
                    else {
                        long long tempResult = first * second;
                        first = tempResult;
                    }
                }
                
                tempNum.push_back(first);
                
                numbers = tempNum;
                opers = tempOper;
            }
            else if (oper == '+') {
                long long first = numbers[0];
                vector<long long> tempNum;
                vector<char> tempOper;
                
                for (int j = 1; j < numbers.size(); j++) {
                    long long second = numbers[j];
                    
                    if (opers[j - 1] != oper) {
                        tempOper.push_back(opers[j - 1]);
                        tempNum.push_back(first);
                        first = second;
                    }
                    else {
                        long long tempResult = first + second;
                        first = tempResult;
                    }
                }
                
                tempNum.push_back(first);
                
                numbers = tempNum;
                opers = tempOper;
            }
            else if (oper == '-') {
                long long first = numbers[0];
                vector<long long> tempNum;
                vector<char> tempOper;
                
                for (int j = 1; j < numbers.size(); j++) {
                    long long second = numbers[j];
                    
                    if (opers[j - 1] != oper) {
                        tempOper.push_back(opers[j - 1]);
                        tempNum.push_back(first);
                        first = second;
                    }
                    else {
                        long long tempResult = first - second;
                        first = tempResult;
                    }
                }
                
                tempNum.push_back(first);
                
                numbers = tempNum;
                opers = tempOper;
            }
        }
        
        long long result = numbers[0];
        
        if (result < 0) {
            result = -result;
        }
        
        return result;
    }
    
    long long result = -1;
    for (int i = 0; i < used.size(); i++) {
        if (!tempUsed[i]) {
            temp.push_back(i);
            tempUsed[i] = true;
            result = max(result, solve(temp, tempUsed, numbers, opers));
            tempUsed[i] = false;
            temp.pop_back();
        }
    }
    
    return result;
}

long long solution(string expression) {
    long long answer = 0;
    
    vector<long long> numbers;
    vector<char> opers;
    
    map<char, bool> mp;
    int expSize = expression.size();
    string number = "";
    for (int i = 0; i < expSize; i++) {
        char c = expression[i];
        
        if ('0' <= c && c <= '9') {
            number += c;
        }
        else {  // operator
            if (mp[c] == false) {
                used.push_back(c);
            }
            opers.push_back(c); 
            mp[c] = true;
            
            numbers.push_back(stoll(number));
            number = "";
        }
    }
    
    if (opers.size() == 1) {
        long long result;
        if (opers[0] == '-') {
            result = numbers[0] - numbers[1];
        }
        else if (opers[0] == '+') {
            result = numbers[0] + numbers[1];
        }
        else {
            result = numbers[0] * numbers[1];
        }
        
        if (result < 0) {
            result = -result;
        }
        
        return result;
    }
    
    numbers.push_back(stoll(number));
    
    answer = solve(vector<int>(), vector<bool>(mp.size(), false), numbers, opers);
    
    return answer;
}