[Programmers] Lv2.수식 최대화

• 이 글은 C++로 풀이를 작성하였습니다

문제

예시

---

풀이

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	vector<long long> result;
	void findMaxnum(vector<long long> num, vector<char> operation, vector<char> oper, bool check[3]){
	// 숫자 하나만 남았을 경우
	if(num.size()==1){
	result.push_back(abs(num[0]));
	}
	// 숫자 하나 이상 남았을 경우, 즉 연산이 더 해야하는 경우
	else{
	// 연산의 종류를 확인하여 backtraking으로 구현
	for(int i=0;i<oper.size();i++){
	if(!check[i]){
	check[i]=true;
	vector<long long> tempnum = num; // 현재 숫자 배열
	vector<long long> newnum; // 나중 숫자 배열
	vector<char> newoperation; // 나중 연산 배열
	// 연산 배열들을 모두 순회하여 현재 연산의 종류와 같은 경우를 찾는다
	for(int j=0;j<operation.size();j++){
	// 같을 경우
	// 연산자의 갯수에 +1만큼 숫자 갯수가 있다.
	// 또한 같은 연산자일 경우 앞이 우선순위이기 때문에 계산 결과를 앞 배열에 둔다.
	if(operation[j] == oper[i]){
	if(oper[i] == '*'){
	tempnum[j+1] = tempnum[j]*tempnum[j+1];
	}
	else if(oper[i] == '-'){
	tempnum[j+1]=tempnum[j]-tempnum[j+1];
	}
	else{
	tempnum[j+1]=tempnum[j]+tempnum[j+1];
	}
	}
	// 다를 경우 연산자 뒤에 있는 숫자는 더 이상 연산에 사용되지 않기 때문에 newnum 배열에 추가
	// operation도 연산이 진행하지 않았기 때문에 newoperation 배열에 추가
	else{
	newnum.push_back(tempnum[j]);
	newoperation.push_back(operation[j]);
	}
	}
	newnum.push_back(tempnum[tempnum.size()-1]); // 마지막 숫자 넣기
	findMaxnum(newnum,newoperation,oper,check);
	check[i]=false;
	}
	}
	}
	}
	long long solution(string expression) {
	long long answer=0;
	vector<long long> num; // 숫자 배열
	vector<char> operation; // 숫자사이의 모든 연산자 배열
	vector<char> oper; // 연산자들의 종류 배열 ( 중복 x )
	bool check[3]={0}; // dfs로 순열 구현 (next_permutaion으로도 구현 가능)
	string str="";
	// expression을 num, operation, oper 배열 채우기
	for(int i=0;i<expression.size();i++){
	if(isdigit(expression[i])){
	str+=expression[i];
	}
	else{
	num.push_back(stoi(str));
	str.clear();
	operation.push_back(expression[i]);
	if(find(oper.begin(),oper.end(),expression[i])==oper.end()){
	oper.push_back(expression[i]);
	}
	}
	}
	num.push_back(stoi(str));
	// dfs로 순열구현하는 방식과 유사하게 확인
	findMaxnum(num,operation,oper,check);
	answer = *max_element(result.begin(),result.end());
	return answer;
	}

view raw Programmers Lv2.operation max.cpp hosted with ❤ by GitHub

• 추가로 궁금한점이나 수정할 부분 있으면 댓글로 남겨주세요.