프로그래머스 레벨2 <수식 최대화> C++ 풀이

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

프로그래머스

 

사실 문제를 처음 읽으면서 못풀것같다라는 생각이 들었습니다. 연산자 & 문자열이 믹스된 문제들은 항상 어려웠던 기억이 있어서 시작부터 사실 쫄고 들어갔습니다. 근데 막상 끝까지 읽어보니 풀만한 문제라는 생각이 들었습니다. 그래도 지금까지 이런 문제 유형을 풀어보려고 노력했던게 도움이 되었던 것 같습니다. 연산자 우선순위와 문자열이 가미된 문제들은 풀어 볼 만한 것이 많기 때문에 많이 풀어보시면 충분히 풀만한 문제라고 생각이듭니다.

 

문제로 들어가보면 결국 + - * 이 세 연산자를 우선순위를 어떻게 매기냐에 따라 입력으로 주어지는 문자열의 수식의 값이 달라지고, 그에 따라 계산한 값중 절대값이 가장 큰 값을 리턴하는 문제였습니다.

 

생각보다는 단순합니다. 저 역시 완탐으로 나올 수 있는 모든 경우의 수를 조합해보면 금방 구할 수 있다고 생각하고 풀어내려갔습니다. + - * 의 우선순위를 나누는 경우의 수는 6가지의 경우의 수밖에 나오지 않습니다. 마치 1 2 3이라는 숫자의 순열과 같습니다( 3! ). 

 

연산해주는 함수 calcul을 만들었습니다. 인자로는 입력받은 수식과 +-*가 의 6가지가 string으로 저장되어있는 배열을 돌기위한 인덱스를 넘겨줍니다. 그리고 중요한 포인트인 두개의 vector를 만듭니다. 하나는 char형으로 + - * 연산자만 받고, 하나는 계산된 식을 받을 겁니다.

 

먼저 for문으로 입력 수식을 돌면서 숫자와 연산자를 구분해서 넣어줍니다. 그리고 인자로 넘겨받은 인덱스를 통해 +-* 6가지중 하나를 가져와서 순서대로 for문을 돕니다. 숫자와 연산자가 둘다 순서대로 벡터에 들어있기 때문에, 지금 순서의 연산자를 만나면 그 순서에 맞는 수가들어있는 val벡터의 숫자에 연산을 진행하고, 앞에 벡터에 연산된 결과를 넣어주면서 그 뒤에있던 숫자를 벡터에서 erase해줍니다. 그리고 인덱스 순서가 꼬이지 않게 다시 for문을 돌 수 있도록 i--를 해줍니다.

 

모든 연산이 끝나게되면 단 하나의 숫자만 val벡터에 남게됩니다. 그리고 최대값과 비교롤해서 더 큰 값이면 갱신해주는 식으로 6가지 모든 경우의 수를 돌고 나오면 최대값을 구할 수 있습니다 !

 

 

#include <string>
#include <vector>
#include <queue> //100-60000-520
 
using namespace std;
 
//완탐
//벡터 두개 - > 연산자 벡터 , 계산값 벡터
 
 
string opr[6] = { "+*-","+-*","-+*","-*+","*+-","*-+" };
long long maxVal = -100000;
 
void calcul(int idx, string exp)
{
    string cur = opr[idx];
    vector<string> val;
    vector<char> op;
 
    string frag = "";
    for (int i = 0; i < exp.length(); i++)
    {
        if (i == exp.length() - 1)
        {
            frag += exp[i];
            val.push_back(frag);
        }
        if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*')
        {
            val.push_back(frag);
            frag = "";
            op.push_back(exp[i]);
        }
        else
        {
            frag += exp[i];
        }
    }
 
    for (int i = 0; i < 3; i++)
    {
        char tmp = cur[i];
        int size = op.size();
        for (int i = 0; i < size; i++)
        {
            if (i >= op.size())
            {
                break;
            }
            if (tmp == op[i])
            {
                if (tmp == '-')
                {
                    long long tmp2 = stoull(val[i]) - stoull(val[i + 1]);
                    val[i] = to_string(tmp2);
                    val.erase(val.begin() + i + 1);
                    op.erase(op.begin() + i);
                    i--;
                }
                else if (tmp == '+')
                {
                    long long tmp2 = stoull(val[i]) + stoull(val[i + 1]);
                    val[i] = to_string(tmp2);
                    val.erase(val.begin() + i + 1);
                    op.erase(op.begin() + i);
                    i--;
                }
                else
                {
                    long long tmp2 = stoull(val[i]) * stoull(val[i + 1]);
                    val[i] = to_string(tmp2);
                    val.erase(val.begin() + i + 1);
                    op.erase(op.begin() + i);
                    i--;
                }
            }
        }
 
    }
    
    long long maxSub = stoull(val[0]);
    if (maxSub < 0)
        maxSub *= -1;
    if (maxSub > maxVal)
        maxVal = maxSub;
}
 
long long solution(string expression) {
    
    for (int i = 0; i < 6; i++)
    {
        calcul(i, expression);
    }
 
    return maxVal;
}