프로그래머스 - 수식 최대화 (Lv.2)

문제 링크

• 👉 수식 최대화

문제 설명

• 중위표기법으로 수식이 하나 주어진다.
• 연산자의 종류는 +, -, * 3가지이며 우선순위를 가진다. 수식에 포함된 연산자의 종류는 1~3개가 가능하다.
• 우선순위는 각자 다르며 우선순위를 정할 수 있는 최대 경우의 수는 3!=6 개 이다.
• 수식의 결과값은 항상 절댓값을 취한다.
• 수식의 최댓값을 구하라

문제 접근1

• 연산자를 담는 배열과 피연산자(정수)를 담는 배열을 만든다.
• 수식에 등장한 연산자만을 찾고, 가능한 조합을 찾는다.
• 각 경우의 수마다 수식 계산을 진행하는데, 우선순위가 높은 연산자부터 수식의 앞에서부터 연산을 진행한다.

구현1(All Pass)

#include <string>
#include <vector>
#include <cctype>
#include <memory.h>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

vector<char> allCase, cand, op;
vector<long long> num;
long long ans = 0, result = 0;
bool visited[3] = {false, };

// 숫자가 작을수록 높은 우선순위
int getPriority(char oper){
    for(int i=0; i<cand.size(); i++){
        if(cand[i]==oper) return i;
    }
}

void getResult(vector<char> iop, vector<long long> inum){
    if(iop.size()==0) {
        result = abs(inum[0]);
        cout << result << endl;
        return;
    }
    
    vector<char> nop;
    vector<long long> nnum;
    // 가장 높은 우선순위 연산자 찾기
    int priority = getPriority(iop[0]);
    for(int i=1; i<iop.size(); i++){
        int np = getPriority(iop[i]);
        if(priority > np) priority = np;
    }
    
    bool flag = true;
    long long val;
    int idx = 0;
    for(int i=0; i<iop.size(); i++){
        if(priority==getPriority(iop[i]) && flag){
            if(iop[i]=='+') val = inum[idx] + inum[idx+1];
            else if(iop[i]=='-') val = inum[idx] - inum[idx+1];
            else if(iop[i]=='*') val = inum[idx] * inum[idx+1];
            nnum.push_back(val);
            idx+=2;
            flag = false;
        }
        else{
            nnum.push_back(inum[idx++]);
            nop.push_back(iop[i]);
        }
    }
    
    getResult(nop, nnum);
}

void setPriority(int v){
    if(cand.size()==allCase.size()) {
        // 수식 계산
        vector<char> iop = op;
        vector<long long> inum = num;
        getResult(iop, inum);
        ans = max(ans, result);
        return;
    }
    
    for(int i=0; i<allCase.size(); i++){
        if(visited[i]) continue;
        visited[i]=true;
        cand.push_back(allCase[i]);
        setPriority(i+1);
        cand.pop_back();
        visited[i]=false;
    }
}

long long solution(string expression) {
    long long answer = 0;
    
    // 0: +, 1: -, 2: *
    vector<char> opCount(3,0);
    string tmp;
    for(int i=0; i<expression.length(); i++){
        char ch = expression[i];
        if(isdigit(ch)) tmp.push_back(ch);
        else {
            num.push_back(stoll(tmp));
            tmp.clear();
            op.push_back(ch);
            if(ch=='+') opCount[0]++;
            else if(ch=='-') opCount[1]++;
            else if(ch=='*') opCount[2]++;
        }
    }
    num.push_back(stoll(tmp));
    if(opCount[0]>0) allCase.push_back('+');
    if(opCount[1]>0) allCase.push_back('-');
    if(opCount[2]>0) allCase.push_back('*');
    
    setPriority(0);
    answer = ans;
    return answer;
}

• 코드 길이가 길고, 고득점을 받지 못한 코드

문제 접근2 (다른사람 풀이참고)

• 우선순위에 따른 연산자 조합은 최대 6가지가 가능하다.
• 이때 6가지 경우의 수 안에는 연산자 종류가 1개, 2개인 경우에 대해서도 모두 포함되어 있다.
• 따라서 6가지 경우의 수를 미리 정의해두고 정의된 연산자 조합의 앞에 위치한 연산자부터 수식을 계산하면 연산자 우선순위가 높은 순서대로 계산할 수 있다.
• 1번 코드처럼 한번에 하나의 연산만 진행하지 않고, 연산자 우선순위가 높은 연산자들을 한번에 모두 계산할 수 있도록 한다.
• 처음 문제에서 주어진 연산자와 피연산자(정수) 배열은 연산자 조합에 따라 수식을 계산할 때마다 같은 수식을 유지할 수 있도록 해야한다.
• 연산을 진행하게 되면 연산자 배열과 피연산자(정수) 배열의 길이 변화가 있다는 점에 유의하여 인덱스를 조정해야한다.
• 벡터 STL 중 하나인 erase() 함수를 통해 연산에 참여한 2개의 연산자중 하나를 지운다.

구현

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

// 가능한 연산자 조합
vector<string> candOp = {"+-*", "+*-", "-+*", "-*+", "*+-", "*-+"};

long long getValue(string prior, vector<char>& top, vector<long long>& tnums){
    for(int j=0; j<3; j++){
        int idx=0;
        char pr = prior[j];
        for(int t=0; t<top.size(); t++){
            if(pr==top[t]){
                if(pr=='+') tnums[t] += tnums[t+1];
                else if(pr=='-') tnums[t] -= tnums[t+1];
                else if(pr=='*') tnums[t] *= tnums[t+1];
                tnums.erase(tnums.begin()+t+1);
                top.erase(top.begin()+t);
                t--;
            }
        }
    }
    return abs(tnums[0]);
}

long long solution(string expression) {
    long long answer = 0;
    vector<char> op;
    vector<long long> nums;
    string tmp;
    for(int i=0; i<expression.length(); i++){
        char ch = expression[i];
        if(isdigit(ch)) tmp.push_back(ch);
        else {
            nums.push_back(stoll(tmp));
            tmp.clear();
            op.push_back(ch);
        }
    }
    nums.push_back(stoll(tmp));
    
    for(int i=0; i<6; i++){
        vector<char> top = op;
        vector<long long> tnums = nums;
        string prior = candOp[i];
        answer = max(answer, getValue(prior, top, tnums));
        // cout << answer << endl;
    }
    
    return answer;
}