코딩테스트 : 수식 최대화

이 문제는 주어진 수식에서 연산자 우선순위를 재정의하여 얻을 수 있는 가장 큰 절댓값을 찾는 문제이다.

연산자는 + - *로 구성되어있으며 연산자 우선 순위는 동등하지 않고 무조건 우선순위가 정해져 있다는 특징이 있다.

BFS 방식으로 구현하였으며 우선 순위별로 나올 수 있는 모든 경우의 수 중 최대값을 찾는다.

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

// 두 숫자와 연산자를 이용하여 계산하는 함수
string calculate(string num1, string op, string num2)
{
    if (op == "+")
        return to_string(stoll(num1) + stoll(num2));  // 덧셈
    else if (op == "-")
        return to_string(stoll(num1) - stoll(num2));  // 뺄셈
    else if (op == "*")
        return to_string(stoll(num1) * stoll(num2));  // 곱셈

    return "";  // 에러 발생 시 빈 문자열 반환
}

// 주어진 우선순위에 따라 연산을 수행하는 함수 (op는 1:+, 2:-, 3:*)
void calOperate(vector<string>& v, int op)
{
    string operate;
    
    if (op == 1)
        operate = "+";  // op가 1이면 덧셈 연산
    else if (op == 2)
        operate = "-";  // op가 2이면 뺄셈 연산
    else if (op == 3)
        operate = "*";  // op가 3이면 곱셈 연산
    
    for(int i = 1; i < v.size(); i+=2)  // 연산자들을 순회
    {
        if(v[i] == operate)  // 현재 연산자가 우선순위에 해당하는 연산자와 같으면
        {
            v[i-1] = calculate(v[i-1], v[i], v[i+1]);  // 이전 숫자와 다음 숫자를 계산
            v.erase(v.begin() + i, v.begin() + i + 2);  // 계산에 사용된 연산자와 다음 숫자 제거
            i -= 2;  // 인덱스 조정
        }
    }

    return;  // 결과 반환 (실제로는 사용되지 않음)
}

// BFS를 사용하여 모든 우선순위 조합에 대해 계산하고 최대값을 찾는 함수
long long bfs(vector<string> v)
{
    long long max = 0;  // 최대값 저장 변수
    
    queue<pair<vector<string>, vector<int>>> q;  // 큐 생성 (수식과 우선순위 조합 저장)
    q.push(make_pair(v, vector<int>()));  // 초기 수식과 빈 우선순위 조합을 큐에 삽입
    
    while(!q.empty())  // 큐가 비어있지 않으면 반복
    {
        pair<vector<string>, vector<int>> tempA = q.front();  // 큐에서 수식과 우선순위 조합을 가져옴
        q.pop();  // 큐에서 제거
        
        for(int i = 1; i <= 3; i++)  // 3가지 연산자에 대해 반복
        {
            pair<vector<string>, vector<int>> temp = tempA;  // 현재 수식과 우선순위 조합 복사
            if(find(temp.second.begin(), temp.second.end(), i) != temp.second.end())
                continue;  // 이미 사용한 우선순위 조합이면 건너뜀
            
            calOperate(temp.first, i);  // 현재 우선순위로 계산
            
            if(temp.first.size() == 1)  // 계산 결과가 하나만 남으면 (최종 결과)
            {
                long long num = stoll(temp.first[0]);  // 숫자로 변환
                if(num < 0)
                    num = num * -1;  // 음수면 절댓값으로 변환
                max = num > max ? num : max;  // 최대값 갱신
            }
            
            temp.second.push_back(i);  // 현재 우선순위 조합에 추가
            
            q.push(temp);  // 큐에 삽입
        }
    }

    return max;  // 최대값 반환
}

// 주어진 수식에서 최대 상금을 계산하는 함수
long long solution(string expression) {
    vector<string> v;  // 숫자와 연산자를 저장할 벡터
    string temp;  // 임시 문자열

    // 표현식을 숫자와 연산자로 분리
    for (char ch : expression)
    {
        if (isdigit(ch))
        {
            temp += ch;  // 숫자가 계속 나오면 temp에 쌓음
        }
        else
        {
            if (!temp.empty()) {
                v.push_back(temp);  // 이전 숫자가 있으면 벡터에 추가
                temp = "";  // 숫자 처리 후 temp 초기화
            }
            v.push_back(string(1, ch));  // 연산자는 한 문자씩 추가
        }
    }
    if (!temp.empty()) {
        v.push_back(temp);  // 마지막 숫자도 벡터에 추가
    }

    return bfs(v);  // bfs 함수 호출하여 최대값 반환
}