2020 카카오 인턴십-수식 최대화 -C++

문제바로가기

1. 문자열 파싱
2. next_permutation을 활용한 수열 조합으로 계산하기

1.문자열 파싱하기

long long solution(string expression) {
	string n = "";
	for (int i = 0; i < expression.size(); i++) {
		if (expression[i] != '+' && expression[i] != '-' && expression[i] != '*') {
			n += expression[i];
		}
		else {
			numss.push_back(stoi(n));
			n = "";
			opp.push_back(expression[i]);
		}
	}
	numss.push_back(stoi(n));

numss에는 100,200,300,500,20
opp에는 + + 가 들어가있다.

2. 순열계산

sort(v.begin(), v.end());
	do {
		vector <long long>nums;
		vector <char>op;
		nums = numss;
		op = opp;

		for (int i = 0; i < v.size(); i++) {
			char w = v[i];
			for (int j = 0; j < op.size(); j++) {
				if (op[j] == w) {
					if (w == '*') {
						long long tmp = nums[j] * nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin()+j+1);
						op.erase(op.begin() + j);
						j--;
					}
					else if (w == '+') {
						long long tmp = nums[j] + nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin() + j + 1);
						op.erase(op.begin() + j);
						j--;
					}
					else {
						long long tmp = nums[j] - nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin() + j + 1);
						op.erase(op.begin() + j);
						j--;

					}
				}
			}
		}

현재 v라는 vector에는 순열 조합으로 * + - 가 들어가있다.
그래서 op.size()만큼 돌면서 우선순위가 높은게 존재한다면 계산을한다.

100200+300500+20에서
를 해야한다면
는 0번 인덱스 100은 0번인덱스 200은 1번 인덱스이므로,
계산한 값을 nums의 0번 인덱스에 넣고,
erase를 통해서 갱신한다.

		if (abs(nums[0]) > answer) {
			answer = abs(nums[0]);
		}

	} while (next_permutation(v.begin(), v.end()));
    return answer;

마지막으로 abs를 활용하여 answer보다 더 큰지 활용하여 answer를 갱신한다.

전체코드

#include <deque>
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

vector <long long>numss;
vector <char>opp;
vector<long long>s1;
vector<char>s2;
long long answer = 0;
vector<char>v = { '+','-','*' };


long long solution(string expression) {
	string n = "";
	for (int i = 0; i < expression.size(); i++) {
		if (expression[i] != '+' && expression[i] != '-' && expression[i] != '*') {
			n += expression[i];
		}
		else {
			numss.push_back(stoi(n));
			n = "";
			opp.push_back(expression[i]);
		}
	}
	numss.push_back(stoi(n));

	sort(v.begin(), v.end());
	do {
		vector <long long>nums;
		vector <char>op;
		nums = numss;
		op = opp;

		for (int i = 0; i < v.size(); i++) {
			char w = v[i];
			for (int j = 0; j < op.size(); j++) {
				if (op[j] == w) {
					if (w == '*') {
						long long tmp = nums[j] * nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin()+j+1);
						op.erase(op.begin() + j);
						j--;
					}
					else if (w == '+') {
						long long tmp = nums[j] + nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin() + j + 1);
						op.erase(op.begin() + j);
						j--;
					}
					else {
						long long tmp = nums[j] - nums[j + 1];
						nums[j] = tmp;
						nums.erase(nums.begin() + j + 1);
						op.erase(op.begin() + j);
						j--;

					}
				}
			}
		}

		if (abs(nums[0]) > answer) {
			answer = abs(nums[0]);
		}

	} while (next_permutation(v.begin(), v.end()));
    return answer;
}