2020 카카오 인턴 코딩 테스트 - 2번. 수식 최대화(c++)

연산자의 종류를 exp벡터에 넣어주고, 연사자의 위치를 차례대로 location벡터에 넣어준다.

이후, next_permutation으로 exp벡터에 있는 연산자들의 우선순위의 경우 수를 구한다.

do while문 안에서는 임시 벡터를 만들어서 우선순위에 해당되는 연산들은 먼저 계산을 해주고 없애고 하는 식으로 계산을 해준다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
long long solution(string expression) {
    long long answer = 0;
    
    vector<long long> num;
    vector<char> exp, location; // 연산자 종류, 연산자 위치
    
    string s = "";
    for(int i=0; i<expression.size(); i++){
        if(expression[i]=='+' || expression[i]=='-' || expression[i]=='*'){
            num.push_back(stoi(s));
            s = "";
            
            if(find(exp.begin(), exp.end(), expression[i]) == exp.end()){
                exp.push_back(expression[i]);
            }
            location.push_back(expression[i]);
        }else{
            s += expression[i];
        }
    }
    
    num.push_back(stoi(s));
    sort(exp.begin(), exp.end());
    
    do {
        // 매번 계산한 위치를 지우고 하는 작업이 필요하기 때문에 임시 벡터가 필요하다.
        vector<char> tmp_loc = location;
        vector<long long> tmp_num = num;
        
        for(int i=0; i<exp.size(); i++){
            for(int j=0; j<tmp_loc.size(); j++){
                if(exp[i]==tmp_loc[j]){
                    if(exp[i]=='+'){
                        tmp_num[j] = tmp_num[j]+tmp_num[j+1];
                    } else if(exp[i]=='-'){
                        tmp_num[j] = tmp_num[j]-tmp_num[j+1];
                    } else{
                        tmp_num[j] = tmp_num[j]*tmp_num[j+1];
                    }
                    
                    // 계산한 부분 지우기
                    tmp_num.erase(tmp_num.begin()+j+1);
                    tmp_loc.erase(tmp_loc.begin()+j);
                    j--;
                }
            }
        }
        
        // 최대값 갱신
        answer = max(answer, abs(tmp_num[0]));
        
    } while(next_permutation(exp.begin(), exp.end()));
    
    
    return answer;
}

 

참고 자료

eunchanee.tistory.com/88