[프로그래머스][2020 카카오 인턴십][C++] 수식 최대화

문제

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

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

 

---

문제 풀이

접근 방식

연산자의 우선순위를 재정의하여 절댓값이 가장 큰 숫자를 만드는 문제이다.

우선, 주어진 expression을 숫자와 연산자로 분류하여 각각 nums, opers에 저장해주었다.

그 후, next_permutation을 활용하여 연산자의 우선순위를 바꿔가며 결괏값을 구해주었고,

그 결과값의 최댓값을 답으로 제출하였다.

 

연산을 할 때에는 각 연산자의 연산 결괏값을 리턴하는 cal 함수를 만들어서 사용해주었고,

숫자 temp_nums[j]와 temp_nums[j+1]를 temp_opers[j] 연산한 값을 temp_nums[j]에 저장해주었고,

사용한 temp_nums[j+1]과 temp_opers[j]는 erase를 사용하여 제거해주었다.

 

---

풀이 코드 - C++

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

long long cal(long long a, long long b, char c) {
    switch(c) {
        case '*' :
            return a * b;
        case '+':
            return a + b;
        case '-':
            return a - b;
    }
}

long long solution(string expression) {
    vector<char> opers;
    vector<long long> nums;
    int len = expression.size();
    int sidx = 0;
    for (int i = 0; i < len; i++) {
        if (!isdigit(expression[i])) {
            opers.push_back(expression[i]);
            nums.push_back(stoi(expression.substr(sidx, i - sidx)));
            sidx = i + 1;
        }
    }
    nums.push_back(stoi(expression.substr(sidx)));

    
    vector<char> priority = { '*','+','-' };
    int oper_len = opers.size();
    long long answer = 0;
    vector<char> temp_opers;
    vector<long long> temp_nums;
    int temp_len;
    do {
        temp_opers = opers;
        temp_nums = nums;
        temp_len = oper_len;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < temp_len; j++) {
                if(temp_opers[j] == priority[i]) {
                    temp_nums[j] = cal(temp_nums[j], temp_nums[j+1], temp_opers[j]);
                    temp_nums.erase(temp_nums.begin() + j + 1);
                    temp_opers.erase(temp_opers.begin() + j);
                    temp_len--;
                    j--;
                }
            }
        }
        if(answer < abs(temp_nums[0]))
            answer = abs(temp_nums[0]);
    } while (next_permutation(priority.begin(), priority.end()));

    return answer;
}

실행 결과

실행 결과 : 100.0