[알고리즘C++] 수식 최대화

오늘의 문제

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

수식 최대화

나의 풀이

#include <string>
#include <vector>
#include <set>
#include <iostream>
#define abs(x) x<0 ? -x:x

using namespace std;
string per;                            // 조합을 위한 문자열
vector<string> perS ={};             // 완성된 조합 set
bool check[4]= { false, };             // 방문 여부
vector<char>p;                          // 조합 elements

void permutation(int depth){       // n은 원하는 문자열 길이
    if(depth == p.size()){
        perS.push_back(per);         // 완성된 조합 저장
        return;
    }
    for(int i = 0; i < p.size(); i++){
        if(!check[i]){
            check[i] = true;
            per[depth] = p[i];          // 현재 depth에 i번째 문자 저장
            permutation(depth + 1);    // 다음 depth에서 재귀 실행
            check[i] = false;             // 현재 depth에 쓰인 문자 풀어주기
        }
    }
}
long long solution(string expression) {
    long long answer = 0;
    vector<long long> num;
    vector<char> exp;
    set<char> check;
    int idx = 0;
    for(int i=1;i<expression.size();i++){
        if(expression[i]-'0'<0 || expression[i]-'0'>10){
            exp.push_back(expression[i]);
            if(check.insert(expression[i]).second != false){
                p.push_back(expression[i]);
                per+="*";
            }
            num.push_back(stoi(expression.substr(idx, i-idx)));
            idx = i+1;
        }
        if(i == expression.size()-1)
            num.push_back(stoi(expression.substr(idx, i-idx+1)));
    }
    permutation(0);
    
    for(int i=0;i<perS.size();i++){ // 모든 set
        vector<long long> tempN(num);
        vector<char> tempE(exp);
        for(int j=0;j<p.size();j++){ // 각 연산에 대해
            for(int k= 0;k<tempE.size();k++){ // 연산에 대해
                if(tempE[k] == perS[i][j]){ // 그 연산이라면
                    long long n;
                    if(tempE[k] == '+'){
                        n = tempN[k]+tempN[k+1];
                    }else if(tempE[k] == '-'){
                        n = tempN[k]-tempN[k+1];
                    }else{
                        n = tempN[k]*tempN[k+1];
                    }
                    tempN[k] = n;
                    
                    tempE.erase(tempE.begin()+k);
                    tempN.erase(tempN.begin()+k+1);
                    k--;
                }
            }
        }
        answer = max(answer, abs(tempN[0]));
    }
    
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    set<char> s;
    vector<char> all_op;
    vector<char> op;
    vector<long long> num;

    string temp="";
    for(int i=0;i<expression.length();i++) {
        if(!isdigit(expression[i])) {
            s.insert(expression[i]);
            all_op.push_back(expression[i]);
            num.push_back(stoi(temp));
            temp="";
        } else temp+=expression[i];
    }
    num.push_back(stoi(temp));

    set<char>::iterator it;
    for(it=s.begin();it!=s.end();it++) {
        op.push_back(*it);
    }

    do {
        vector<char> temp_op = all_op;
        vector<long long> temp_num = num;

        for(int i=0;i<op.size();i++) {
            for(int j=0;j<temp_op.size();j++) {
                if(temp_op[j]==op[i]) {
                    long long temp;
                    if(op[i]=='*') {
                        temp=temp_num[j]*temp_num[j+1];
                        i--;
                    } else if(op[i]=='+') {
                        temp=temp_num[j]+temp_num[j+1];
                        i--;
                    } else if(op[i]=='-') {
                        temp=temp_num[j]-temp_num[j+1];
                        i--;
                    }

                    temp_op.erase(temp_op.begin()+j);
                    temp_num.erase(temp_num.begin()+j, temp_num.begin()+j+2);
                    temp_num.insert(temp_num.begin()+j, temp);

                }
            }
        }

        if(answer<abs(temp_num.back())) {
            answer=abs(temp_num.back());
        }

    } while(next_permutation(op.begin(), op.end()));

    return answer;
}

배울 점

• 이렇게 긴 코드는 오랜만이다..
• 인덱스가 굉장히 헷갈렸던 것 같다. 그것만 분명하게 해결했으면 금방 끝났을 듯
  [다시 정리]
• 숫자와 수식을 따로 벡터에 담은 후 permutation으로 받아온 조합대로 계산을 한다.
• 계산을 할 때 permutation순서에 맞는 연산만 처리, 연산된 숫자를 넣고 기존 숫자를 지운다. 연산도 마찬가지
• 계산 결과중 제일 큰 값을 return