[프로그래머스] 카카오 인턴 - 수식 최대화

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

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

 

 

[풀이방법]

1. 세개의 연산자 (+, -, *) 의 우선순위를 구한다. 이건 순열 (dfs - next_permutation) 으로 구현가능하다.

2. 구한 각 우선순위에 맞게 계산을 한다.

3. 최대값을 구한다. 

 

2번이 좀 어려웠는데, 단순하게 생각을 해봤다.

우선순위는 3개

최고 우선순위 연산자가 인풋으로 들어온 식의 연산자의 어느 위치에 존재하는 지 찾는다.

만약 2번째 순서에 존재한다면 숫자1 (연산자2) 숫자2 로 계산한 값이 숫자1에 업데이트가 되고 숫자 2는 사라져야한다.

그리고 연산2가 끝났으므로 연산자 2를 지워준다. 이럴 경우, erase 가 자유로운 벡터로 구현한다.

또한, 연산자 총 갯수가 하나 감소했으므로 연산자 인덱스도 -- 해준다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;


long long solution(string expression) {
    long long answer = 0;

    vector <char> ex; ex.clear();
    vector <long long> num; num.clear();
    vector <char> cmd; cmd.clear();

    ex.push_back('*');
    ex.push_back('+');
    ex.push_back('-');
    sort(ex.begin(), ex.end());

    string num_str = "";

    for(int i=0; i<expression.size(); i++) {
        if(expression[i] == '+'|| expression[i] == '-' || expression[i] == '*') {
            cmd.push_back(expression[i]);
            num.push_back(stoi(num_str));
            num_str = "";
        }
        else
            num_str += expression[i];

        if(i == expression.size()-1)
            num.push_back(stoi(num_str));
    }

    do {
        vector <long long> tmp_num = num;
        vector <char> tmp_cmd = cmd;

        for(int i=0; i<ex.size(); i++) {
            for(int j=0; j<tmp_cmd.size(); j++) {
                if(ex[i] == tmp_cmd[j]) {
                    if(tmp_cmd[j] == '+')
                        tmp_num[j] = tmp_num[j] + tmp_num[j+1];
                    else if(tmp_cmd[j] == '-')
                        tmp_num[j] = tmp_num[j] - tmp_num[j+1];
                    else if(tmp_cmd[j] == '*')
                        tmp_num[j] = tmp_num[j] * tmp_num[j+1];

                    tmp_num.erase(tmp_num.begin()+j+1);
                    tmp_cmd.erase(tmp_cmd.begin()+j);
                    j--;
                }
            }
        }

        answer = max(abs(tmp_num[0]), answer);

    }while(next_permutation(ex.begin(), ex.end()));

    return answer;
}