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

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

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

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;

map<char, int> m;
vector<long long> num;
vector<char> op;
vector<int> v={1,2,3};

void splits(string s){
    string const delims{"-+*"};
    size_t beg, pos=0;
    while ((beg=s.find_first_not_of(delims, pos))!=string::npos){
        pos=s.find_first_of(delims, beg+1);
        op.push_back(s[pos]);
        num.push_back(stoll(s.substr(beg,pos-beg)));
    }
}

long long calc(char op, long long a, long long b){
    switch(op){
        case '*':
            return a*b;
        case '+':
            return a+b;
        case '-':
            return a-b;
    }
}

long long stck(string expr){
    stack<long long> n; stack<char> o;
    long long a,b;
    char oper;
    if (num.size()==2 && op.size()==1)
        return calc(op[0], num[0], num[1]);
    n.push(num[0]); n.push(num[1]);
    o.push(op[0]); 
    for (int i=2, j=1; i<num.size(); i++,j++){
        while (!o.empty() && m[o.top()]>=m[op[j]]){ //top보다 우선순위 작거나 같으면 계산
            b=n.top(); n.pop();
            a=n.top(); n.pop();
            oper=o.top(); o.pop();
            n.push(calc(oper, a, b));
        }
        o.push(op[j]);
        n.push(num[i]);
    }
    while (!o.empty()){
        b=n.top(); n.pop();
        a=n.top(); n.pop();
        oper=o.top(); o.pop();
        n.push(calc(oper, a, b));
    }
    return abs(n.top());
}

long long solution(string expression) {
    long long answer = 0;
    int i=0;
    splits(expression);
    do{
        vector<int> temp;
        for (auto it=v.begin(); it!=v.end(); it++)
            temp.push_back(*it);
        m['+']=temp[0]; m['-']=temp[1]; m['*']=temp[2];
        answer=max(answer, stck(expression));
    } while (next_permutation(v.begin(), v.end()));
    return answer;
}

6!의 경우의 수를 따져본다. 경우의 수는 next_permutation으로 구현해서 순열을 만들어주었다.

문자열 수식을 parsing할 때는 find_first_not_of 함수를 사용하였다. 

그리고 우선순위에 맞게 수식을 계산한다. number 수식, operator 수식 스택 2개를 만든다.

연산자 우선순위가 top에 있는 것보다 낮으면, 스택에 있는 수식을 계산한다. (top보다 지금 넣으려는 연산자 우선순위가 높을 때까지). 우선순위가 top보다 높으면 그대로 스택에 넣는다(number, operator 둘다).

그리고 마지막으로 stack이 빌 때까지 수식을 계산하여 리턴한다.

 

 

너무 복잡하게 구현한것 같아 다른 버전으로도 짜봤다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

vector<long long> num;
vector<char> op;
vector<char> priority;
long long answer = 0;
bool visit[3];
char operators[3]={'*','+','-'};

void split(string s){
    string temp="";
    for (int i=0; i<s.size(); i++){
        if (s[i]=='-' || s[i]=='*' || s[i]=='+'){
            op.push_back(s[i]);
            num.push_back(stoll(temp));
            temp="";
            continue;
        }
        temp+=s[i];
    }
    num.push_back(stoll(temp));
}

long long calc(){
    vector<long long> temp_num=num;
    vector<char> temp_op=op;
    for (int i=0; i<3; i++){      //우선순위대로 계산
        for (int j=0; j<temp_op.size(); j++){
            if (temp_op[j]==priority[i]){
                long long a=temp_num[j];
                long long b=temp_num[j+1];
                switch(temp_op[j]){
                    case '*':
                        temp_num[j]=a*b;
                        break;
                    case '+':
                        temp_num[j]=a+b;
                        break;
                    case '-':
                        temp_num[j]=a-b;
                        break;
                }
                temp_num.erase(temp_num.begin()+j+1);
                temp_op.erase(temp_op.begin()+j);
                j--;
            }
        }
    }
    return abs(temp_num[0]);
}

void dfs(int cnt){
    if (cnt==3){
        answer=max(calc(),answer);
        return;
    }
    else{
        for (int i=0; i<3; i++){
            if (visit[i])
                continue;
            visit[i]=true;
            priority.push_back(operators[i]);
            dfs(cnt+1);
            priority.pop_back();
            visit[i]=false;
        }
    }
}


long long solution(string expression) {
    memset(visit, false, sizeof(visit));
    split(expression);
    dfs(0);
    return answer;
}

split을 간단하게 해줬다. 숫자가 아닌 문자를 만나면 그간 저장했던 문자열을 num 벡터에 넣고, 문자는 op 벡터에 넣는 식으로 하였다.

 

경우의 수는 dfs 로 구하여, priority에 넣는다. 수식의 계산은 아까처럼 stack이 아니라 vector을 이용한다.

num이 100, 200, 300, 500, 20 이면

op는 -,*,-,+ 인데 이때 연산자의 인덱스가 0이면 피연산자의 인덱스가 0, 1이 되고 .. 이렇게 진행되기 때문에 for문을 priority 에 돌아 주면서 우선순위가 먼저인 애부터 계산해준다.

계산 결과는 첫번째 피연산자 자리에 저장하고, vector의 erase를 이용해 두번째 피연산자를 삭제하고 연산자도 삭제해준다. 이때 하나씩 땡겨졌으므로 j-- 를 감소시키는게 중요하다.