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

문제 링크: programmers.co.kr/learn/courses/30/lessons/67257

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

1. 주의할 점

- Long Long을 계속 유지하도록 한다

- 헷갈리지 않도록 구현한다

 

2. 구현

- Expression에서 숫자는 Num 벡터에, 연산자는 Op 벡터에 넣는다. 이때, opChar에는 사용된 연산자의 종류를 저장한다

- DFS() 함수를 통해 사용된 연산자에 우선순위를 부여한다

- Cal() 함수에서 Dq와 Qop를 통해 Num과 Op 벡터의 원소를 할당한다

- 모든 연산자에 대한 계산이 끝날때까지 현재 연산자의 우선순위가 Order[K]와 같다면 계산을 수행한다. 이때, 모든 수들은 Long Long 형태를 지니도록 한다

#include <string>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <iostream>
#include <limits.h>
#include <stack>
#include <set>
using namespace std;
int order[3];       //+,-,*
bool check[3]={false,};
vector<char> opChar;
long long result = LLONG_MIN;
vector<long long> num;
vector<char> op;

void cal(){
    deque<long long> dq;
    queue<char> qop;    
    for(int i=0;i<num.size();i++)
        dq.push_back(num[i]);
    for(int i=0;i<op.size();i++)
        qop.push(op[i]);
    
    for(int k=0;k<opChar.size();k++){
        int len = qop.size();
        int cur = order[k];
        stack<long long> s;
        s.push(dq[0]);
        dq.pop_front();
        for(int i=0;i<len;i++){
            char c = qop.front();
            long long cv = dq[0];
            qop.pop();
            dq.pop_front();
            if(c==opChar[cur]){
                long long before = s.top();
                s.pop();
                if(c=='+') before+=cv;
                else if(c=='-') before-=cv;
                else before*=cv;
                s.push(before);
            }
            else{
                s.push(cv);
                qop.push(c);
            }
        }
        while(!s.empty()){
            dq.push_front(s.top());
            s.pop();
        }
    }
    result = max(result,abs(dq[0]));
}

void dfs(int cnt){
    if(cnt==opChar.size()){
        cal();
        return;
    }
    for(int i=0;i<opChar.size();i++){
        if(!check[i]){
            check[i]=true;
            order[cnt]=i;
            dfs(cnt+1);
            check[i]=false;
        }
    }
}

long long solution(string expression) {
    long long answer = 0;
    string str="";
    set<char> s;
    for(int i=0;i<=expression.size();i++){
        if(i==expression.size()){
            num.push_back(stoi(str));
            break;
        }
        char c = expression[i];
        if('0'<=c && c<='9')    str+=c;
        else{
            op.push_back(c);
            s.insert(c);
            num.push_back(stoi(str));
            str="";
        }
    }
    for(auto it = s.begin();it!=s.end();it++){
        opChar.push_back(*it);
    }
    dfs(0);
    return answer=result;
}