[프로그래머스 2020 카카오 인턴십] 수식 최대화

문제

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

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

 

풀이

1. 우선 구해야하는건 + , - , * 의 서로 다른 연산자 우선순위 3!가지 순열을 구성해보고 모든 연산결과의 최소를 구하는 것입니다. 

 

2. 입력으로 받은 문자열에 숫자와 연산자가 섞여있으므로 주어진 식을 파싱해가며 우선순위가 서로 다른 연산자 식을 계산하기 간편하게 중위표기식에서 후위표기식으로 변환해줍니다.

 

3. 중위표기식에서 후위표기식(post)으로 바꾸는건 연산자를 넣어두는 벡터(op)를 사용하며 op는 항상 위쪽의 연산자가 우선순위가 높도록 유지합니다. post로 바꾸는 방법은 아래와 같습니다.

• 현재 보고있는 문자가 연산자일 때, 현재까지 모아놓은 숫자는 그냥 post에 넣어줍니다.

• 현재 보고있는 연산자가 op에 들어있는 연산자보다 우선순위가 작다면 op에 들어있는 연산자를 post에 넣어주고, 현재 보고있는 연산자를 op에 넣어줍니다.

• 입력받은 문자열을 전부 순회한 후, op에 남아있는 연산자는 위쪽부터 post에 담아줍니다. 

4. 마지막으로 계산을 할 때, post에 담긴 숫자들은 따로 숫자들을 담는 벡터(num)에 관리해주며 post를 순회하며 연산자를 만났을 때 num에서 숫자를 두 개 팝하는데 이때 팝해서 나온 숫자는 먼저 나오는 숫자가 연산자 뒤에 나오는 숫자인걸 조심하면 됩니다.

• (ex) 12- 의 경우 1 - 2가 맞는식이지만 num에서 나오는 숫자를 차례대로 계산하면 2 - 1이 됨. 따라서 먼저 나오는 숫자가 연산자 뒤 숫자

풀이

 

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
typedef long long ll;

vector<int> v;

// 연산자를 인덱스로 변환
int conv(string x) {
	if (x == "+") return 0;
	else if (x == "-") return 1;
	return 2;
}

// 앞쪽 연산자의 우선순위가 앞선다면 양수를, 아니면 음수를 반환하는 비교함수
int calop(string a, string b) {
	if (v[conv(a)] > v[conv(b)]) return 1;
	else if (v[conv(a)] < v[conv(b)]) return -1;
	return 0;
}

ll solution(string e) {
	ll ans = 0;
	for (int i = 0; i < 3; i++) v.pb(i);
	do {
		string tmp = "";
		vector<string> post, op; // 연산자우선순위가 op.back()으로 갈수록 커지도록 유지한다.
		vector<ll> num;

		// parsing & convert to postfix
		for (int i = 0; i < sz(e); i++) {
			if (e[i] == '+' || e[i] == '-' || e[i] == '*') {
				string curop = ""; curop += e[i];
				if (!tmp.empty()) post.pb(tmp), tmp = "";
				while (!op.empty() && calop(op.back(), curop) >= 0) {
					post.pb(op.back());
					op.pop_back();
				}
				op.pb(curop);
			}
			else tmp += e[i];
		}
		if (!tmp.empty()) post.pb(tmp);
		while (!op.empty()) post.pb(op.back()), op.pop_back();

		// calculate
		for (int i = 0; i < sz(post); i++) {
			string c = post[i];
			if (c == "+" || c == "-" || c == "*") {
				ll b = num.back(); num.pop_back();
				ll a = num.back(); num.pop_back();
				if (c == "+") num.pb(a + b);
				else if (c == "-") num.pb(a - b);
				else num.pb(a * b);
			}
			else num.pb(stoll(c));
		}
		ans = max(ans, abs(num[0]));
	} while (next_permutation(all(v)));
	return ans;
}