프로그래머스 - 수식 최대화

상반기에 실전에서 매우 애먹었던 문제이다.

다시 풀어보니 쉽게 풀 수 있었는데 깨달은 점이 하나 있었다.

(이런 구현문제는 효율을 크게 생각안하고 시도 하는게 포인트인 것 같다.)

 

일단 연산자가 최대 3개이고 우선순위 경우의 수가 6가지이고

우선순위에 따른 계산 시 시간복잡도는 고려하지 않아도 될정도로 적으므로 (string 최대길이가 100이므로)

마음놓고 dfs 완탐을 해도 된다.

 

당시에 애먹었던 이유는 원본 벡터를 복사한 temp 벡터 하나만 가지고 연산을 하려했었다..

그래서 list를 사용해야하나 아니면 vector로 remove하며 해야하나 고민하는데 시간을 허비했다.

 

굳이 그럴 필요없이

연산자에 의해 계산된 결과를 담는 벡터(t,tt)를 하나 더 이용하면 된다.

연산자의 개수 + 1 = 피연산자의 개수 이고

연산은 순서대로 일어나므로

해당 연산자를 만나면 t의 가장 뒤 피연산자를 꺼낸고 연산후 다시 집어넣어주면 된다.

 

연산이 끝나고 나면 피연산자가 하나 남게되고

그 값을 answer와 비교해준다.

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
 
using namespace std;
vector<long long > v; // 주어진 피연산자를 순서대로 담는 vector
vector<char> oper; // 사용되는 연산자가 무엇인지 구별
vector<char> vv; // 주어진 연산자를 순서대로 담는 vector
int order[3]; // 연산자의 순서를 위한 배열
bool chk[3];
long long answer;
void dfs(int dep) {
    if (dep == oper.size()) {
        long long res = 0;
 
        vector<long long > t;
        vector<char> tt;
        for (int i = 0; i < v.size(); i++) t.push_back(v[i]);
        for (int i = 0; i < vv.size(); i++) tt.push_back(vv[i]);
 
        for (int k = 0; k < oper.size(); k++) {
 
            vector<long long > x;
            vector<char> xx;
 
            x.push_back(t[0]);
            for (int i = 0; i < tt.size(); i++) {
                if (tt[i] == oper[order[k]]) {
                    if (tt[i] == '*') {
                        long long y = x.back();
                        y = y * t[i + 1];
                        x.pop_back();
                        x.push_back(y);
                    }
                    else if (tt[i] == '+') {
                        long long y = x.back();
                        y = y + t[i + 1];
                        x.pop_back();
                        x.push_back(y);
 
                    }
                    else if (tt[i] == '-') {
                        long long y = x.back();
                        y = y - t[i + 1];
                        x.pop_back();
                        x.push_back(y);
                    }
                }
                else {
                    xx.push_back(tt[i]);
                    x.push_back(t[i + 1]);
                }
            }
 
            t.clear(); t.resize(0);
            tt.clear(); tt.resize(0);
 
            for (int i = 0; i < x.size(); i++) t.push_back(x[i]);
            for (int i = 0; i < xx.size(); i++) tt.push_back(xx[i]);
        }
 
 
        if (abs(t[0]) > answer) answer = abs(t[0]);
 
 
        return;
 
    }
    for (int i = 0; i < oper.size(); i++) {
        if (!chk[i]) {
            chk[i] = true;
            order[dep] = i;
            dfs(dep + 1);
            chk[i] = false;
        }
    }
}
long long solution(string expression) {
    answer = 0;
 
    string tmp = "";
    unordered_map<char, bool> mp;
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] == '-' || expression[i] == '+' || expression[i] == '*') {
            v.push_back(stoll(tmp));
            vv.push_back(expression[i]);
            tmp = "";
            if (mp.count(expression[i]) == 0) {
                oper.push_back(expression[i]);
                mp[expression[i]] = true;
            }
        }
        else {
            tmp += expression[i];
        }
    }
    v.push_back(stoll(tmp));
 
    memset(chk, false, sizeof(chk));
 
    
    dfs(0);
 
    return answer;
}