Programmers [2020 카카오 인턴십] : 수식 최대화 풀이 및 코드

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

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

수식을 입력받아서, 연산자의 우선순위를 정하고 계산하는 문제이다 !!

수식 연산자는 더하기 빼기 곱하기의 세 가지만 있기 때문에 next_permutation 함수를 이용해서 우선순위를 이용했다

계산 과정은 N, N+1번째 피연산자를 N번째 연산자로 계산해서 N번째 피연산자로 교체하면 된다

후위연산식의 계산 과정은 생각이 났는데, 중위연산식이 생각이 잘 안 났기 때문에 그냥 벡터연산을 이용해서 풀이했다

 

수도코드는 다음과 같다

 

그냥 raw하게 코딩했는데 카카오 테크 블로그에 올라온 모범풀이와 비교해 봐야겠다... 😓

+ 딱히 특별한 접근법이 없는 단순 구현문제 !! 하지만 이 문제는 토큰분리 때문에 C++보다 java가 더 나을듯 ..?

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

using namespace std;

long long calculate(vector<long long> num, vector<char> op, vector<char> rank) {
	for (auto x : rank) {
		for (int i = 0; i < op.size(); i++) {
			if (op[i] == x) {
				vector<long long>::iterator it = num.begin()+i;
				long long one=*it,two=*(it+1);
				num.erase(it,it+2); 

				long long result = 0;
				if (x == '*')
					result = one * two;
				else if (x == '-')
					result = one - two;
				else result = one + two;

				it = num.begin() + i;
				num.insert(it, result);
				vector<char>::iterator ct = op.begin() + i;
				op.erase(ct);
				i--;
			}
		}
	}
	return abs(num[0]);
}

long long solution(string expression) {
	long long answer = 0;
	char str[101];
	vector<char> op;
	vector<long long> num;

	strcpy(str, expression.c_str());
	char* ptr = strtok(str, "+-*");
	

	while (ptr != NULL) {
		num.push_back(atoi(ptr));
		ptr = strtok(NULL, "+-*");
	}
	for (auto x : expression) {
		if (!(x >= '0' && x <= '9'))
			op.push_back(x);
	}

	vector<char> rank{ '*','+','-' };

	do {
		long long k=calculate(num, op, rank);
		if (k > answer)answer = k;
	} while (next_permutation(rank.begin(), rank.end()));

	return answer;
}

시간복잡도: O(N)

expression의 길이를 N이라 할 때, 연산자의 길이는 (N/2)이므로 f(n) = 3! * 3 * (N/2) 이므로 (N! = N^N)

다행히 연산자의 개수는 상수(3)로 고정되어 있기 때문에 시간복잡도는 매우 낮다