수식최대화(2020 카카오 인턴십)

문제 링크

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

 

 

풀이

연산자(long long)와 피연산자(char)를 미리 vector 컨테이너에 담고 "+-*"를 순열로 돌리면서 해당 연산자와 같으면 계산하고 다르면 넘어가는 식으로 구현하였다.

연산 순서가 있기 때문에 스택에 넣어서 pop_back()하는 식으로 구현하였다.

next_permutation()함수를 사용하여 모든 조건을 검사하였다.

 

 

#include <string>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    vector<long long> num;        // operand
    vector<char> oper;        // operator
    string condition = "*+-";
    
    // 담기
    int k = 0;
    for (int i = 0; i < expression.length(); i++)
    {
        if (!(expression[i] >= '0' && expression[i] <= '9')) // '+', '-', '-'
        {
            oper.push_back(expression[i]);
            num.push_back(stoi(expression.substr(k, i - k)));
            k = i + 1;
        }
    }
    // 후 처리
    num.push_back(stoi(expression.substr(k)));
    
    do
    {
        long long result = 0;
        vector<long long> lVector(num);
        vector<char> cVector(oper);
        
        for(int i=0; i<3; i++)
        {
            vector<long long> lV;
            vector<char> cV;
            
            int k = 0;
            lV.push_back(lVector[k++]);
            for(char c : cVector)
            {
                lV.push_back(lVector[k++]);
                if(c == condition[i])
                {
                    long long next = lV.back();
                    lV.pop_back();
                    long long prev = lV.back();
                    lV.pop_back();
                    
                    switch(c)
                    {
                        case '*': lV.push_back(prev*next); break;
                        case '+': lV.push_back(prev+next); break;
                        case '-': lV.push_back(prev-next); break;
                    }
                }
                else cV.push_back(c);
            }
            swap(lV, lVector);
            swap(cV, cVector);
        }
        result = lVector.back();
        result = result > 0 ? result : -result;
        // cout<<"result = "<<result <<endl;
        answer = answer > result ? answer : result;
    }
    while(next_permutation(condition.begin(), condition.end())) ;
    
    return answer;      // 우승 시 받을 수 있는 가장 큰 금액
}