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

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

빠르게 푸는 연습을 해야하는데 쉽지않다.

풀이 방법은 다음과 같다.

1. 인풋 expression을 모두 정수형으로 변환해준다. (num 배열에 담아줌)

• isdigit이 true일 동안 문자를 더해주고, 연산자가 등장하는 순간 더해진 문자들을 출력하면 연산자와 연산자 사이의 숫자가 된다.
• 연산자는 0, 1, 2로 매핑해준다.

2. *, -, + 중 등장한 연산자들에 대해서 combination을 구해준다.

• 셋 다 등장했다면 6가지 조합이 존재 ( [0, 1, 2], [0, 2, 1] ... )

3. 해당 조합을 순회하면서 우선순위에 맞게 연산을 수행해준다.

• 이 때, num 배열의 홀수번째 인덱스에만 연산자가 올 수 있으므로 홀수 번째마다 연산자를 체크한다.
  - i번째라 가정하고, 우선순위에 맞는 연산자라면 i - 1, i + 1번째 숫자에 대해서 해당 연산을 진행해준다.
• 이 후, i - 1번째에 해당 값을 insert 해주고, i번째 인덱스를 3번 지워준다.
  - 예를 들어, 1 + 5 - 2 + 1 이었고, - 연산을 수행했다고 가정하면 1 + 3 + 1이 되도록 해준다.
• 지운 후 i 값을 1 줄여줘야 함.

4. 조합에 대해서 모든 연산이 끝날 때마다 max 값을 업데이트 해준다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int candidate[102];
int visit[102];
vector<vector<int>> op_set;
void combination(int n, int depth, const vector<int> &op)
{
    if(n == depth) {
        vector<int> tmp;
        for(int i=0;i<depth;i++) 
            tmp.push_back(op[candidate[i]]);
        op_set.push_back(tmp);
        return;
    }
    for(int i=0;i<n;i++) {
        if(visit[i] == 1) 
            continue;
        visit[i] = 1;
        candidate[depth] = i;
        combination(n, depth + 1, op);
        visit[i] = 0;
    }
}
long long solution(string expression) {
    long long answer = 0;
    
    int unique[3] = { 0, 0, 0 };
    map<char, int> m;
    m['+'] = 0; m['*'] = 1; m['-'] = 2;
    
    string tmp = "";
    vector<long long> num;
    vector<int> op;
    for(auto it : expression) {
        if(isdigit(it)) {
            tmp += it;
        } else {
            int idx = m[it];
            num.push_back(stoi(tmp));
            num.push_back(idx);
            if(unique[idx] == 0) {
                op.push_back(idx);
                unique[idx] = 1;
            }
            tmp = "";
        }
    }
    num.push_back(stoi(tmp));
    
    combination(op.size(), 0, op);
    
    for(auto it : op_set) {
        vector<long long> init_num(num.begin(), num.end());
        for(int i=0;i<it.size();i++) {
            for(int j=0;j<init_num.size();j++) {
                if((j & 1) && init_num[j] == it[i]) {
                    long long new_num;
                    if(it[i] == 0) 
                        new_num = init_num[j - 1] + init_num[j + 1];
                    else if(it[i] == 1)
                        new_num = init_num[j - 1] * init_num[j + 1];
                    else
                        new_num = init_num[j - 1] - init_num[j + 1];
                    init_num.insert(init_num.begin() + j - 1, new_num);
                    for(int k=0;k<3;k++)
                        init_num.erase(init_num.begin() + j);
                    j--;
                }
            }
        }
        answer = max(abs(init_num[0]), answer);
    }
    return answer;
}