문제

next_permutation을 사용해 모든 연산자 우선순위 순열에 대해 답을 구했다.

next_permutation을 사용할 때는 해당 배열이 정렬된 상태여야 하는데, 이 사실을 간과해 테케 1번을 계속 통과 못하고 있었다..

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long calc(long long a, long long b, char opr) {
	if (opr == '+') return a + b;
	else if (opr == '-') return a - b;
	else return a * b;
}

long long solution(string expression) {
	long long answer = 0;
	vector<long long> nums;
	vector<char> oprs;
	vector<char> opr_list = { '+', '-', '*' };
	int i, j;
	string num = "";

	for (i = 0; i < expression.size(); i++) {
		if ('0' <= expression[i] && expression[i] <= '9') num += expression[i];
		else { // 연산자
			oprs.push_back(expression[i]);
			nums.push_back(stoll(num));
			num = "";
		}
	}
	nums.push_back(stoll(num));

	sort(opr_list.begin(), opr_list.end()); // next_permutation을 사용하기 위해서는 벡터가 정렬된 상태여야 함
	do {
		vector<long long> tmp_nums = nums;
		vector<char> tmp_oprs = oprs;

		for (i = 0; i < 3; i++) {
			for (j = 0; j < tmp_oprs.size(); j++) {
				if (tmp_oprs[j] == opr_list[i]) {
					tmp_nums[j] = calc(tmp_nums[j], tmp_nums[j + 1], opr_list[i]);
					tmp_nums.erase(tmp_nums.begin() + (j + 1));
					tmp_oprs.erase(tmp_oprs.begin() + j);
					j--;
				}
			}
		}

		if (abs(tmp_nums.front()) > answer) answer = abs(tmp_nums.front());
	} while (next_permutation(opr_list.begin(), opr_list.end()));
	return answer;
}