[프로그래머스 C++] 수식 최대화

 

[프로그래머스 C++] 수식 최대화

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

순열 Permutation, 조합 Combination

문자열

 

do

while(next_permutation(v.begin(), v.end()))

---

 

정답 코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<long long> v; // 숫자
vector<char> oper;  // 연산자
long long answer; // 최종 결과값
 
// Calculate 함수는 두 개의 숫자와 한 개의 연산자를 입력으로 받아 연산 결과를 반환.
long long Calculate(long long a, long long b, char op)
{
    if (op == '+') return a + b;
    else if (op == '-') return a - b;
    else if (op == '*') return a * b;
}
 
long long solution(string ex) {
    int n = ex.size();
 
    string num = "";
    for(int i=0; i<n; i++)
    {
		if('0' <= ex[i] && ex[i] <= '9'){
            num += ex[i];
		}
        else{
            oper.push_back(ex[i]);      // 연산자를 oper 벡터에 저장
            v.push_back(stoll(num));    // 숫자를 v 벡터에 저장
            num = "";
        }
    }
    v.push_back(stoll(num)); // 마지막 숫자를 v 벡터에 추가
 
    // 모든 연산자의 우선순위를 고려하기 위해 순열을 사용
    vector<int> idx = { 0, 1, 2 };
    string op = "+-*";
    do{
        // 원본 벡터 v와 oper의 복사본을 만듬
        vector<long long> numValue = v;
        vector<char> tempOper = oper;
 
        // 각 연산자 우선순위에 따라 계산을 수행합니다.
        for(int i = 0; i < 3; i++){ // "+-*"
            for (int j = 0; j < tempOper.size();) {
		        if(tempOper[j] == op[idx[i]]) 
		        {                
                    long long result = Calculate(numValue[j], numValue[j + 1], tempOper[j]); // 두 숫자를 선택하여 해당 연산자로 계산
 
                    // 계산에 사용된 두 숫자를 numValue 벡터에서 제거
                    numValue.erase(numValue.begin() + j);
                    numValue.erase(numValue.begin() + j);
                    numValue.insert(numValue.begin() + j, result); // 계산 결과를 numValue 벡터에 삽입
                    
                    tempOper.erase(tempOper.begin() + j); // 사용된 연산자를 tempOper 벡터에서 제거
                }
                else
                    j++;  // 해당 연산자가 아닐 경우 다음 인덱스로 이동
            }
        }
        answer = max(answer, abs(numValue[0])); 
    }
    while (next_permutation(idx.begin(), idx.end())); // 모든 연산자의 순열을 고려
 
    return answer;
}

 

 

---