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

 

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

코딩테스트 연습 - 수식 최대화

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

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

using namespace std;

long long findResult(vector<long long> numbers, vector<char> calculate, vector<char> priority) {

	long long result = 0;

	for (char temp : priority) {

		while (true) {
			int location = find(calculate.begin(), calculate.end(), temp) - calculate.begin();
			if (calculate.size() == location) {
				break;
			}
			calculate.erase(calculate.begin() + location);
			long long cal;
			if ('+' == temp) {
				cal = numbers[location] + numbers[location + 1];
			}
			else if ('-' == temp) {
				cal = numbers[location] - numbers[location + 1];
			}
			else if ('*' == temp) {
				cal = numbers[location] * numbers[location + 1];
			}
			numbers[location] = cal;
			numbers.erase(numbers.begin() + location + 1);
		}
	}
	
	result = abs(numbers[0]);
	return result;
}

int dfs(vector<char> &character, vector<char> &priority, vector<vector<char>> &priority_result) {

	if (character.size() == priority.size()) {
		priority_result.push_back(priority);
		return 0;
	}


	for (int i = 0; i < character.size(); i++) {
		vector<char>::iterator it = find(priority.begin(), priority.end(), character[i]);
		if (priority.end() == it) {
			priority.push_back(character[i]);
			dfs(character, priority, priority_result);
			priority.pop_back();;
		}
	}
	return 0;

}

int makeStack(string &expression, vector<long long> &numbers, vector<char> &calculate) {

	int numberLocation = 0;
	int count = 0;
	for (int i = 0; i < expression.size(); i++) {
		if (('+' == expression[i]) || ('-' == expression[i]) || ('*' == expression[i])) {
			string temp = expression.substr(numberLocation, count);
			numbers.push_back(stoi(temp));
			count = 0;
			numberLocation = i + 1;
			calculate.push_back(expression[i]);
		}
		else {
			count++;
		}
	}
	string temp = expression.substr(numberLocation, count);
	numbers.push_back(stoi(temp));

	return 0;
}



long long solution(string expression) {
	long long answer = 0;
	vector<long long> numbers;
	vector<char> calculate;

	makeStack(expression, numbers, calculate);


	vector<char> character{ '+', '-', '*' };
	vector<char> priority;
	vector<vector<char>> priority_result;
	long long result = 0;

	dfs(character, priority, priority_result);

	for (vector<char> temp : priority_result) {
		long long result = findResult(numbers, calculate, temp);
		if (answer < result) {
			answer = result;
		}
	}



	return answer;
}

꾸준히 하다보면 실력이 늘겠지..