[C++] level2 수식최대화 67257

📌수식최대화

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

문제 처음 보자마자 우선 숫자와 연산자를 구분하여 보관해야겠다는 생각이 들었다.
문제에서 연산자가 3개일 때 3!, 2개일 때 2!를 보고 모든 연산자를 돌아야 하므로 연산자 배열을 별도로 생성하여 순열을 계산하고, 각 순열을 통과하여 얻은 결과 값을 비교하여 높은 값을 return 하는 식으로 구현해야겠다 싶었다!

stack으로 담아둘까 하다가 그러면 우선순위대로 계산하지 못하고 원하는 부분의 연산자나 문자열을 꺼낼 수 없기 때문에 queue 도 생각해보았지만 vector가 적당한 것 같아서 vector로 담고 계산한 문자들은 erase로 지우도록 구현하였다. (다들 이렇게 구하는 것 같았다)

연산자의 우선순위는 next_permutation() STL 함수를 이용하여 순열을 통해 구하였다.

next_permutation() ?
: 어떤 연속성을 띈 자료구조(배열 or 백터)의 원소들로 순열을 구하는 함수
현재 나열된 수열에서 다음 순열을 구하고 true를 반환.
더이상 순열이 없다면 false를 반환

📌코드

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

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

long long solution(string expression)
{
    long long max = 0;
    vector<char> oper_list = {'*', '+', '-'}; //연산자 우선순위
    vector<long long> numbers;                //숫자
    vector<char> opers;                       //연산자
    string number = "";

    //연산자와 숫자를 구분하여 vector에 담음
    for (int i = 0; i < expression.size(); i++)
    {
        if (expression[i] == '+' || expression[i] == '*' || expression[i] == '-')
        {
            opers.push_back(expression[i]);
            numbers.push_back(stoi(number));
            number = ""; //다시 초기화
        }
        else
            number += expression[i];
    }
    numbers.push_back(stoi(number)); //마지막 연산자 이후의 숫자를 넣어주기 위해

    //순열을 이용하여 각 연산자를 우선순위에 따라 계산
    do
    {
        vector<long long> tmp_nums = numbers; //복사
        vector<char> tmp_oper = opers;        //복사
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < tmp_oper.size(); j++)
            {
                if (tmp_oper[j] == oper_list[i])
                {
                    tmp_nums[j] = calc(tmp_nums[j], tmp_nums[j + 1], oper_list[i]);
                    tmp_nums.erase(tmp_nums.begin() + j + 1);
                    tmp_oper.erase(tmp_oper.begin() + j);
                    j--;
                }
            }
        }
        //max 값을 연산자 우선순위에 따라 변경될 때마다 바꿔줌
        if (abs(tmp_nums.front()) > max)
            max = abs(tmp_nums.front()); //max 값 변경
    } while (next_permutation(oper_list.begin(), oper_list.end()));

    return max;
}

회고

정리하는 습관을 꼭꼭 새겨두자.

지난 번에 next_permutation() 를 이용하여 문제를 풀었던 기억이 있는데
오늘도 문제를 보고 순열 이걸로 구해서 하면 되겠다는 알았지만
함수명이 기억이 가물가물해서 next 뭐....더라 .... 하면서 next_이런 식으로 구글링했다 ... 바보바보가 따로 없다 .. ㅎㅎ ............

---

참고자료