[프로그래머스] 수식 최대화 문제풀이 c++

 

스택을 이용하여 문제를 풀었다.

먼저 주어진 string을 숫자와 연산자로 구분하여 vector에 push_back한다.

연산자는 {+,-,*}를 각각 0,1,2로 바꾸어 저장하였다.

 

가능한 경우의 수는 최대 3!=6개로 DFS로 재귀를 돌리는 것보다

미리 가능한 경우의 수를 p배열에 만들어 놓고 사용하는 게 효율적이다.

 

count_op로 사용된 연산자 개수를 저장했고, 

count_op가 1일 때는 p배열의 0번 index만 탐색한다.

count_op가 2일때는 p배열의 0번, 1번 index를 탐색한다.

0번은 {0,1,2} 1번은 {2,1,0}이므로 사용된 연산자가 0,1/0,2/1,2일 때 1,0/2,0/2,1을 모두 탐색할 수 있다.

 

 연산자를 저장할 스택 op와 숫자를 저장할 스택 num이 있다.

num의 개수가 op보다 1많으므로 num에 첫번째 숫자를 먼저 push한다.

op가 비어있다면 op와 num에 바로 push한다.

op.top이 j번째 연산자의 우선순위보다 크거나 같다면,

op가 empty()일때까지 num과 op에서 pop하면서 연산을 수행한다(while문)

이 때, op.top보다 연산자의 우선순위가 작으면 break한다.

연산을 수행하고, 해당연산이 j번째 연산자와 같으면 break한다.

 

operand를 전체 탐색하고 나면, 최종 결과는 num.top에 저장되어있고

해당 결과의 절대값과 answer를 비교하여 최대값을 구할 수 있다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    vector<int> number, operand;
    string x= "";
    bool check_op[3] = {false, false, false};
    for(int i=0; i<expression.size(); i++){
        if(isdigit(expression[i]))
            x += expression[i];
        else{
            number.push_back(stoi(x));
            x = "";
            if(expression[i]=='+'){
                check_op[0] = true;
                operand.push_back(0);
            }
            else if(expression[i]=='-'){
                check_op[1] = true;
                operand.push_back(1);
            }
            else{
                check_op[2] = true;
                operand.push_back(2);
            }
        }
    }
    number.push_back(stoi(x));
    
    int count_op = 0;
    for(auto x:check_op)
        if(x)
            count_op++;
    if(count_op == 3)
        count_op = 6;
    
    int p[6][3] = {{0,1,2},{2,1,0},{1,0,2},{2,0,1},{1,2,0},{0,2,1}};
    stack<long long> num;
    stack<int> op;
    for(int i=0; i< count_op; i++){
        num.push(number[0]);
        for(int j=0; j<operand.size(); j++){
            if(op.empty()){
                num.push((long long)number[j+1]);
                op.push(operand[j]);
            }
            else{
                if(p[i][op.top()] >= p[i][operand[j]]){
                    while(!op.empty()){
                        int tmp_op = op.top();
                        long long tmp_num = num.top();
                        if(p[i][tmp_op]<p[i][operand[j]])
                            break;
                        num.pop();
                        if(tmp_op == 0){
                            tmp_num += num.top();
                        }   
                        else if(tmp_op == 1){
                            tmp_num = num.top() - tmp_num;
                        }
                        else{
                            tmp_num *= num.top();
                        }
                        num.pop();
                        op.pop();
                        num.push(tmp_num);
                        if(tmp_op == operand[j]){
                            break;
                        }
                    }
                }
                num.push((long long)number[j+1]);
                op.push(operand[j]);
            }
        }
        while(!op.empty()){
            long long tmp = num.top();
            num.pop();
            if(op.top() == 0)
                tmp += num.top();
            else if(op.top() == 1)
                tmp = num.top() - tmp;
            else
                tmp *= num.top();
            num.pop();
            op.pop();
            num.push(tmp);
        }
        long long res = abs(num.top());
        num.pop();
        answer = max(res, answer);
    }
    
    return answer;
}