수식 최대화(순열, 완전 탐색)

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

프로그래머스

 

각 연산들의 우선순위를 정할때 순열의 개념을 사용한다.

연산자가 3개뿐이라 순열의 경우의 수는 3! = 6가지 뿐이지만 next_permutation 연습을 위해서 굳이 사용해보았다.

 

숫자와 연산자를 각각 다른 벡터에 담아두도록 한다.

순열(우선순위)에 따라 연산자 벡터를 선형 탐색하면서 높은 우선순위의 연산자 먼저 처리해주면 되는데

i번째 연산자는 i번째 숫자와 i+1번째 숫자의 연산이라는 점만 떠올리면 된다.

 

next_permutation 함수의 사용법을 기억하도록 하자.

do {
		//반복문 내용
} while (next_permutation(oper_priority, oper_priority + 3));
// 벡터의 경우 vector.begin()과 vector.end()를 파라미터로 전달

 

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

// 0: +
// 1: -
// 2: *

long long calculate(int oper_priority[], vector<long long> num, vector<int> oper)
{
	for (int i = 0; i < 3; i++)
	{
		int current_oper = oper_priority[i];
		int vec_size = oper.size();
		for (int index = 0; index < vec_size; index++)
		{
			if (oper[index] == current_oper)
			{
				long long cal = 0;
				switch (current_oper)
				{
				case 0:
					cal = num[index] + num[index + 1];
					break;
				case 1:
					cal = num[index] - num[index + 1];
					break;
				case 2:
					cal = num[index] * num[index + 1];
					break;
				}
				num[index] = cal;
				num.erase(num.begin() + (index + 1));
				oper.erase(oper.begin() + index);
				vec_size -= 1;
				index -= 1;
			}
		}
	}
	return num.front();
}

long long solution(string expression)
{
	vector<long long> num;
	vector<int> oper;
	long long temp = 0;
	for (char ch : expression)
	{
		switch (ch)
		{
		case '+':
			num.push_back(temp);
			temp = 0;
			oper.push_back(0);
			break;
		case '-':
			num.push_back(temp);
			temp = 0;
			oper.push_back(1);
			break;
		case '*':
			num.push_back(temp);
			temp = 0;
			oper.push_back(2);
			break;
		default:
			temp *= 10;
			temp += (long long)(ch - '0');
			break;
		}
	}
	num.push_back(temp);

	long long answer = 0;
	int oper_priority[3] = { 0, 1, 2 };
	do {

		long long calret = calculate(oper_priority, num, oper);
		if (abs(answer) < abs(calret)) answer = calret;

	} while (next_permutation(oper_priority, oper_priority + 3));
	return abs(answer);
}