하루 하루는 성실하게
인생 전체는 되는대로

[프로그래머스] 수식 최대화

2 minute read

문제 설명

/* 중략 */
예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다. 대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다. 반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

제한사항

  • expression은 길이가 3 이상 100 이하인 문자열입니다.
  • expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
    • 즉, “402+-561*“처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
  • expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
    • 즉, “100-2145*458+12”처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
    • “-56+100”처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
  • expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
  • 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
  • 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

풀이

40분
순열을 이용하여 연산자 우선순위를 구하고, 해당 연산자 우선순위를 적용했을 때 계산값을 적용하여 최대값을 갱신해주었다. 알고리즘 방법 자체는 간단하지만, 구현하는 과정에서 조금 버벅이게되어 시간이 조금 걸렸다. stringstream을 이용해서 input을 받는 부분과, 숫자 벡터와 기호벡터를 순회하면서 하나씩 지워주는 과정에서 고민했었다.

코드

// 01:54 ~ 02:35
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

long long max_val = -1;
char op_arr[3] = {'+','-','*'};
vector<long long> num;
vector<char> op;
vector<int> seq;

void calc(){
    vector<long long> local_num(num);
    vector<char> local_op(op);
    
    for(int i =0;i<3;++i){
        char now_op = op_arr[seq[i]];
        for(int j =0; j< local_op.size(); ++j){
            if(local_op[j] == now_op){
                if(now_op == '*'){
                    local_num[j] *= local_num[j + 1];
                }
                else if(now_op == '+'){
                    local_num[j] += local_num[j + 1];
                }
                else if(now_op == '-')
                    local_num[j] -= local_num[j + 1];
                local_num.erase(local_num.begin() + j + 1);
                local_op.erase(local_op.begin() + j);
                --j;
            }
        }
    }
    if(local_num[0] < 0) local_num[0] *= -1;
    if(local_num[0] > max_val) max_val = local_num[0];
}
void permute(){
    if(seq.size() == 3){
        calc();
        return;
    }
    
    for(int i =0; i<3; ++i){
        if(seq.empty() || find(seq.begin(),seq.end(),i) == seq.end()){
            seq.push_back(i);
            permute();
            seq.pop_back();
        }
    }
}

long long solution(string expression) {
    for(int i =0; i<expression.length(); ++i){
        if(expression[i] == '*' || expression[i] == '+' || expression[i] == '-'){
            op.push_back(expression[i]);
            expression[i] = ' ';
        }
    }
    
    stringstream ss(expression);
    int n;
    while(ss >> n){
        num.push_back(n);
    }
    permute();
    return max_val;
}

You may also enjoy