[프로그래머스][Level2][C++][next_permutation] 2020 카카오 인턴십- 수식 최대화 - 컴도리돌이

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

 

1.  주어진 문자열에서 숫자와 수식을 구분하여 각 벡터에 저장한다. (first_job 함수에서 처리) -> stringstream으로 문자열을 처리하였고 처음에 나오는 숫자를 먼저 숫자 벡터에 push를 한 후에 반복문을 사용하여 순차적으로 수식과 숫자를 각 벡터에 저장한다.
2.  주어진 문자열을 숫자와 수식을 구분하였으면, 다음 함수 second_job으로 이동한다.
3.  next_permutation을 사용하였고, 수식은 최대 3개 이기 때문에 경우의 수는 6가지 밖에 안나와서 시간초과에 대한 문제는 발생하지 않는다. 
4. 연산 후에는 두 피연산자를 삭제하고 연산자도 삭제한다. 연산 결과는 해당 자리에 삽입한다.
5. 각 경우의 수가 끝날 때마다 answer 변수와 비교하여 가장 큰 값을 return 한다.

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

long long calc(long long a,long long b,char c)
{
    if(c == '+') return a+b;
    else if(c == '-') return a-b;
    else if(c == '*') return a*b;
    else return 0;
}
void first_job(string expression,vector<long long>& number,vector<char>& op)
{
    stringstream ss(expression);
    long long value;
    char o;
    ss >> value;
    number.push_back(value);
    while(ss >> o >> value) number.push_back(value),op.push_back(o);
}

long long second_job(vector<long long>& number, vector<char>& op)
{
    long long answer = 0;
    vector<char> basic_operation = {'*','+','-'};
    do
    {
        vector<long long> temp = number;
        vector<char> temp_op = op;
        for(int i=0; i<3; i++)
            for(int j=0; j<temp_op.size(); j++)
                if(basic_operation[i] == temp_op[j])
                {
                    temp[j] = calc(temp[j],temp[j+1],temp_op[j]);
                    temp.erase(temp.begin()+j+1);
                    temp_op.erase(temp_op.begin()+j);
                    j--;
                }
        answer = max(temp.front(),max(temp.front() * (-1),answer));
    }while(next_permutation(basic_operation.begin(),basic_operation.end()));
    return answer;
}
long long solution(string expression) {
    vector<long long> number;
    vector<char> op;
    first_job(expression,number,op);
    return second_job(number,op);
}