(프로그래머스 c++ KAKAO)수식 최대화

완전 탐색으로 풀어야 한다.

 

문자열 형태의 숫자를 int형으로 바꿔서 저장하기 위한 vector<long long> num.

문자열 형태의 숫자를 저장하는 string n.

연산자의 위치를 나타내는 vector<char> location.

연산자의 종류를 나타내는 vector<char> exp.

 

for문을 통해 expression을 순회한다.

만약 expression[i]가 연산자라면 num 벡터에 n을 int형으로 바꿔서 넣어준 후, n = ""으로 초기화 해준다.

그리고 exp 벡터에서 해당 연산자가 있는지 검사를 하여 중복이 없으면 exp에 넣어준다.

location에는 해당 연산자의 위치를 넣어줘야 하기 때문에 i를 넣어주도록 한다.

 

만약 expression[i]가 연산자가 아니라면 숫자를 나타내므로 n += expression[i]를 계속 해주도록 한다.

 

for문이 끝나면 마지막 숫자가 들어가지 않았기 때문에 num.push_back(n)을 해주어 넣어주도록 한다.

그리고 next_permutation을 하기 위해 연산자들을 sort해주도록 한다.

 

이제 순열을 이용하여 연산자의 우선순위를 지정한다.

임시 저장 벡터인 tmp_num과 tmp_loc을 선언하여 각각 num과 location을 넣어준다.

이중 for문으로 연산자의 우선순위에 따라 식을 계산하도록 한다.

tmp_num[j] 와 tmp_num[j + 1]이 해당 연산자가 위치한 숫자 앞뒤를 나타내기 때문에 tmp_num[j]에 계산한 값을 넣어주고,

tmp_num[j + 1]은 지워주도록 한다.

또한 tmp_loc[j]도 지워주도록 한다.(해당 위치의 연산은 수행했기 때문)

tmp[0]에는 최종적으로 계산한 결과값이 저장되기 때문에

절대값을 씌워 answer과 비교하면 된다...!

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

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    vector<long long> num;
    vector<char> exp, location;
    string n = "";
    
    for(int i = 0; i < expression.size(); i++)
    {
        if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*')
        {
            num.push_back(stoi(n));
            n = "";
            if(find(exp.begin(), exp.end(), expression[i]) == exp.end())
                exp.push_back(expression[i]);
            location.push_back(expression[i]);
        }
        else
            n += expression[i];
    }
    
    num.push_back(stoi(n));
    sort(exp.begin(), exp.end());
    
    do
    {
        vector<long long> tmp_num = num;
        vector<char> tmp_loc = location;
        
        for(int i = 0; i < exp.size(); i++)
        {
            for(int j = 0; j < tmp_loc.size(); j++)
            {
                if(exp[i] == tmp_loc[j])
                {
                    if(tmp_loc[j] == '+')
                        tmp_num[j] = tmp_num[j] + tmp_num[j + 1];
                    else if(tmp_loc[j] == '-')
                        tmp_num[j] = tmp_num[j] - tmp_num[j + 1];
                    else if(tmp_loc[j] == '*')
                        tmp_num[j] = tmp_num[j] * tmp_num[j + 1];
                    
                    tmp_num.erase(tmp_num.begin() + j + 1);
                    tmp_loc.erase(tmp_loc.begin() + j);
                    j--;
                }
            }    
        }
        
        if(answer < abs(tmp_num[0]))
            answer = abs(tmp_num[0]);
    } while(next_permutation(exp.begin(), exp.end()));
    
    return answer;
}