[2020 카카오 인턴십 코딩테스트] 수식 최대화

분류 

시뮬레이션

 

요구사항

최대로 만들수 있는 숫자 구하기

 

풀이

1. 부호 combination 으로 순서정하기

2. 정한 우선순위에 따라 계산하기

 

나는 deque 자료구조를 이용하여 우선 순위의 연산자가 나오면 

원래 deque에서 front

새로운 deque에서 back을 꺼내어서 계산 한후 

다시 새로운 deque에 자료구조를 넣는 식으로 우선 순위를 처리하였다

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>

using namespace std;

vector<string> GetString(string str){
	vector<string> ret;
	string temp;
	for(int i=0 ; i < str.size() ; i++){
		char nowtemp = str[i];
		if(nowtemp >= 48 && nowtemp <=57){
			temp+=nowtemp;
		}
		else{
			if(temp.empty()){
				string strtemp;
				strtemp+=nowtemp;
				ret.push_back(strtemp);
			}
			else{
				ret.push_back(temp);
				temp.clear();
				string strtemp;
				strtemp+=nowtemp;
				ret.push_back(strtemp);

			}
		}
	}
	ret.push_back(temp);
	return ret;
}
void GetExp(vector<string>& Exp, string str){
	int flag=0;
	if(str == "+" || str== "-" || str=="*"){
		char ch;
		if(str=="+") ch='+';
		else if(str=="-") ch='-';
		else if(str=="*") ch='*';
		int flag=0;
		for(auto j: Exp){
			if(j==str){
				flag=1;
				break;
			}
		}
		if(flag==0) Exp.push_back(str);
	}
	else return;
}



long long solution(string expression) {
    long long answer = 0;
	vector<string> ans;
	vector<string> Exp;
	ans=GetString(expression);
	for(auto i : ans){
		GetExp(Exp,i);
	}
	sort(Exp.begin(),Exp.end());
	do{
		deque<string> temp;
		deque<string> ntemp;
		long long tempans=0;
		for(auto i :ans) temp.push_back(i);
		for(auto i : Exp){
		//현재 연산자가 나오면 연산 실시한다.
			int Temp_Size = temp.size();
			for(int j=0 ; j<Temp_Size; j++){
				string Now_str = temp.front();
				temp.pop_front();
				//다르면 새로운 공간에 넣고
				if(Now_str != i){
					ntemp.push_back(Now_str);
				}
				//같으면 연산 실시하고 널는다
				else if(Now_str==i){
					//연산은 원래꺼 제일 앞쪽꺼하고 새로운쪽 제일 뒤쪽하고 실시한다.
					long long Temp_num;
					long long Back_num = stoll(temp.front());
					temp.pop_front();
					j++;
					long long Front_num = stoll(ntemp.back());
					ntemp.pop_back();
					if(i=="*"){
						Temp_num=Front_num*Back_num;
					}
					else if(i=="+"){
						Temp_num=Front_num+Back_num;
					}
					else if(i =="-"){
						Temp_num=Front_num-Back_num;
					}
					//계산한 뒤 새로운 쪽 제일 뒤에 넣는다
					ntemp.push_back(to_string(Temp_num));
				}
			}
			//한 사이클이 완료 되면 원래 스택은 비어있고 새로운 스택으로 이동했을거다 새로운거를 원래로 복사
			temp.clear();
			temp=ntemp;
			ntemp.clear();
		}
		//다 한 경우 temp에 제일 앞에 있는 것이 결과이다
		long long Temp_Result = abs(stoll(temp.front()));
		answer=max(answer,Temp_Result);
	}while(next_permutation(Exp.begin(),Exp.end()));

    return answer;
}