(C++) - 프로그래머스(2020 카카오 인턴십) : 수식 최대화

https://programmers.co.kr/learn/courses/30/lessons/67257

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

brute force 문제였습니다.

 

📕 풀이방법

📔 풀이과정

 1. expression으로부터 숫자, 연산자를 각각 분리해 vector 변수 nums, loc에 각자 push_back해줍니다. 그리고 사용되는 연산자의 종류를 vector변수 priority에 push해줍니다.

 

 2. 연산자들이 모여있는 priority를 사전순으로 정렬해줍니다.

 

 3. next_permutation함수로 우선순위를 계속 바꿔주며 다음을 수행합니다. 

 

  3-1. 주어진 우선순위 배열과 나온 전체 연산자들이 들어있는 loc을 모두 확인합니다. 가장 높은 우선순위는 가장 왼쪽에 있다고 가정하고 수행합니다. 

 

  3-2. 현 우선순위와 같은 모든 loc에 존재하는 연산자들에 대해 연산을 수행하고 erase함수를 통해 왼쪽에 있는 인덱스에 계산결과를 합해줍니다.

 

  3-3. 계산 완료후 절댓값의 최댓값을 answer변수에 저장합니다.

 

📔 정답출력

answer를 반환해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
vector <long long> nums;
vector <char> ops, pri = {'+', '-', '*'};

long long getRes(long long a, char o, long long b){
    if(o == '+') return a + b;
    if(o == '-') return a - b;
    return a * b;
}

long long solution(string expression) {
    nums.clear();
    ops.clear();
    
    sort(pri.begin(), pri.end());
    
    long long answer = 0;
    string tmp;
    for(auto e : expression){
        if(e == '+' || e == '-' || e == '*') {
            ops.push_back(e);
            nums.push_back(stoll(tmp));
            tmp = "";
        }
        else tmp += e;   
    }
    nums.push_back(stoll(tmp));
    
    vector <char> op;
    vector <long long> num;
    
    do{
        num = nums;
        op = ops;
        for(int i = 0; i < pri.size(); i++){
            int sz = op.size();
            for(int j = 0; j < op.size(); j++){
                if(pri[i] == op[j]){
                    long long res = getRes(num[j],op[j],num[j+1]);
                    num.erase(num.begin() + j);
                    op.erase(op.begin() + j);
                    num[j] = res;
                    j--;
                }
            }
        }
        answer = max(answer, abs(num[0]));
    }while(next_permutation(pri.begin(), pri.end()));
    
    return answer;
}