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

[문제]

programmers.co.kr/learn/courses/30/lessons/67257

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

 

[풀이]

 

next_permutation 함수를 사용해 완전탐색으로 풀었다.

 

먼저 vector에 숫자와 연산자를 구분해서 담아줬다.

그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다.

 

우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식으로 풀었다.

 

 

---

 next_permutation 함수 : 순열을 구한다.

예를 들어 집합 { '+' , '-' , '*' }의 모든 순열을 구하면 아래와 같이 총 6가지가 나오게 된다.

 

{ '+' , '-' , '*'}

{ '+' , '*' , '-'}

{ '-', '+' , '*' }

{ '-' , '*' , '+'}

{ '*' ,'+' , '-' }

{ '*'  , '-' , '+'}

[코드]

 

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

using namespace std;

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

long long solution(string expression) {
    long long answer = 0;
    vector <char> oper_list =  { '*', '+', '-' };
    vector <long long> number;
    vector <char> oper;
    string num = "";
    

    for(int i=0;i<expression.size();i++)
    {
        if(expression[i] == '+' || expression[i] =='*' || expression[i] == '-')
        {
            oper.push_back(expression[i]);
            number.push_back(atoi(num.c_str()));
            num="";
        }
        else    num+= expression[i];  
    }
    number.push_back(atoi(num.c_str()));
    long long _max =0;
    do{
        vector <char> tmp_oper = oper;
        vector <long long> tmp_num = number;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<tmp_oper.size();j++)
            {
                if(tmp_oper[j] == oper_list[i])
                {
                    tmp_num[j] = calc(tmp_num[j],tmp_num[j+1],oper_list[i]);
                    tmp_num.erase(tmp_num.begin()+j+1);
                    tmp_oper.erase(tmp_oper.begin()+j);
                    j--;
                }
            }
        } 
        if(_max < abs(tmp_num[0]))   _max = abs(tmp_num[0]);
    }while(next_permutation(oper_list.begin(),oper_list.end()));
    answer = _max;
    return answer;
}