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

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

 

우선 주어진 string을 num과 cal(연산자) vector에 각각 나누어 저장한다.

num={100,200,300,500,20}

cal={-,*,-,+}

방문이 필요한 연산자에 대해서는 visit 배열을 0으로 변경하여, 나중에 방문할 때 1로 변경하는 용도로 사용한다.

 

그 후 func를 돌리는데, 적용 가능한 연산자, 즉 우선순위로 먼저 적용할 연산자를 선정하여 계산한다.

처음에는 *부터 계산하므로, 

num_temp={100,60000,500,20}

cal_temp={-,-,+}

이런 결과가 나올 것이며 그 결과를 func에 다시 돌린다.

 

연산자 벡터가 비었다면, 즉 모든 계산을 끝마쳤다면 현재 answer와 비교하여 최댓값을 저장하면 된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

long long answer = -999;
char op[]={'*','+','-'};

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

void func(vector<long long int>num, vector<char>cal, int visit[])
{
    if (cal.empty())//기호 벡터가 비었다면
    {
        if (num[0] < 0)
            num[0] = -num[0];//절댓값
        if (num[0] > answer)
            answer = num[0];
    }
    else
    {
        for(int i=0;i<3;i++)
        {
            if(!visit[i])//방문하지 않았다면(=우선순위 적용 연산자가 있다면)
            {
                visit[i]=1;
                vector<long long int>num_temp;
                vector<char>cal_temp;
                char c=op[i];
                for (int i = 0; i < cal.size(); i++)
                {
                    if (cal[i] == c)
                    {
                        if (num_temp.size() == cal_temp.size())
                            num_temp.push_back(calc(num[i],num[i+1],c));
                        else
                        {
                            long long int a = num_temp.back();
                            num_temp.pop_back();
                            num_temp.push_back(calc(a,num[i+1],c));
                        }
                    }
                    else
                    {
                        if (num_temp.size() == cal_temp.size())
                            num_temp.push_back(num[i]);
                        else
                            num_temp.push_back(num[i + 1]);
                        cal_temp.push_back(cal[i]);
                    }
                }
                func(num_temp, cal_temp,visit);
                visit[i]=0;
            }
        }
    }
}

long long solution(string expression) {
    vector<long long int>num;//숫자 저장 벡터
    vector<char>cal;//연산기호 저장 벡터
    int visit[]={1,1,1};//방문 필요한 연산기호 0으로 변경, 방문시 1로 변경
    int save = 0;
    for (int i = 0; i < expression.size(); i++)
    {
        char c = expression[i];
        if (isdigit(c))
        {
            if (!save)//여태 저장한게 없다면
                save = c - '0';
            else
                save = 10 * save + (c - '0');
        }
        else//연산 기호라면
        {
            num.push_back(save);
            save = 0;//저장한 숫자 초기화
            cal.push_back(c);
            if(c=='*')
                visit[0]=0;
            else if(c=='+')
                visit[1]=0;
            else if(c=='-')
                visit[2]=0;
        }
    }
    num.push_back(save);

    func(num, cal, visit);
    return answer;
}