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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

 

 

풀이

주어진 수식을 연산자와 피연산자로 나눈다.

모두 나눴으면 각각의 연산자 우선순위에 따른 연산을 수행하여 최댓값을 구하면 된다.

 

for문은 총 6 * 3 * n만큼 돌게 된다.

6은 연산자 우선순위의 경우의 수이고

3은 +, -, *

n은 수식에 포함되어 있는 연산자의 개수이다.

 

연산자 우선순위에 따라 순서대로 계산을 수행한다.

피연산자의 개수는 항상 연산자의 개수 + 1이기 때문에

i번째 연산자는 i와 i+1의 피연산자에 사용된다.

 

예를 들어,

operands = [50, 6, 3, 2]

operators = [*, -, *]가 존재할 때 연산자 우선순위가 * - + 순서라면

operands의 0번 인덱스인 50과 1번 인덱스인 6을 계산할 때에

operators의 0번 인덱스인 *가 사용된다.

 

계산된 연산자, 피연산자들은 모두 erase 시켜주고 결과값은 연산자의 i번째 인덱스에 다시 저장한다.

모든 연산이 끝났을 때 연산자 배열의 첫 값에 모든 연산의 결과값이 들어있다.

 

이 값에 절댓값을 씌워 최댓값을 갱신한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

long long calc(long long a, long long b, char oper){
    long long ret;
    
    if(oper == '-'){
        ret = a - b;
    }
    else if(oper == '*'){
        ret = a * b;
    }
    else{
        ret = a + b;
    }
    
    return ret;
}

long long solution(string expression) {
    long long answer = 0;
    vector<long long> operands; //피연산자
    vector<char> operators; //연산자
    string priorityArray[6] = {"*-+", "*+-", "+*-", "+-*", "-+*", "=*+"};
    
    string tmp = "";
    for(int i=0; i<expression.size(); i++){
        if(expression[i] <= '9' && expression[i] >= '0'){
            tmp += expression[i];
        }
        else {
            operands.push_back(stoi(tmp));
            tmp = "";
            
            if(expression[i] == '+') operators.push_back('+');
            else if(expression[i] == '-') operators.push_back('-');
            else operators.push_back('*');
        }
    }
    operands.push_back(stoi(tmp));
    
    for(int i=0; i<6; i++){
        string priority = priorityArray[i];
        vector<long long> copiedOperands = operands;
        vector<char> copiedOperators = operators;
        
        for(int j=0; j<3; j++){
            for(int k=0; k<copiedOperators.size(); k++){
                if(copiedOperators[k] == priority[j]){
                    copiedOperands[k] = calc(copiedOperands[k], copiedOperands[k+1], copiedOperators[k]);
                    
                    copiedOperands.erase(copiedOperands.begin() + k + 1);
                    copiedOperators.erase(copiedOperators.begin() + k);
                    
                    k--;
                }
            }
        }
        
        answer = max(abs(copiedOperands.front()), answer);
    }
    
    return answer;
}