2020 카카오 인턴쉽 코딩테스트 2번 수식 최대화

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

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

2020 카카오 인턴쉽 코딩테스트에 출제되었었던 수식 최대화 문제이다.

위 링크를통하여 프로그래머스에서 풀어볼 수 있다.

 

아이디어

100-200*300-500+20 과 같이 수식이 주어졌을때 수학적 우선순위를 따지지 않고 연산의 우선순위를 임의로 정하여 가장 큰 값이 나오도록하는 문제이다.

dfs으로 완전탐색 하여 수식이 가질 수 있는 모든 우선순위 케이스를 탐색하여 풀이하면 된다.

이 문제는 최근 다시 카카오 코테 문제를 풀어보는 도중 이전에 풀었던 기록이 있었는데 정확히 1년전에 엉성하게 풀었던 기록이 남아 있어서 너무 인상 깊었다. 꾸준히 공부를 하면서 조금씩은 아주 조금씩은 성장을 하고 있는 중이구나 조급해하지 말고 우직하게 나가자라는 생각이 많이 들었다.

 

 

#include <string>
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;
vector<char> ex;
vector<long long> nums;
pair<string, bool> oper[3] = { {"+",false}, {"-",false}, {"*",false} };
long long maxIdx;

long long max(long long  a, long long b) { return a > b ? a : b; }

//연산자랑 숫자주면 계산해주는 함수
long long getResult(char ex, long long a, long long b) {
	switch (ex)
	{
	case '*':
		return a * b;

	case '+':
		return a + b;

	case '-':
		return a - b;
	}
}

//연산의 순서가 정해지면 계산시작
long long cal(string exp) {
	vector<char> tempEx = ex;
	vector<long long> tempNums = nums;
	for (int i = 0; i < 3; i++) {
		for (int e = 0; e < tempEx.size(); e++) {
			//연산 순서에 맞는 연산이 나올때
			if (exp[i] == tempEx[e]) {
				//숫자2개 연산자 하나로 계산하기 때문에 계산 결과를 첫번째 숫자 vector에 넣고 숫자와 연산자 하나씩 삭제
				tempNums[e] = getResult(tempEx[e], tempNums[e], tempNums[e + 1]);
				tempNums.erase(tempNums.begin() + e + 1);
				tempEx.erase(tempEx.begin() + e);
				e--;
			}
		}
	}
	return abs(tempNums[0]);
}

void dfs(string exp) {
	//연산의 순서가 정해지면
	if (exp.size() == 3) {
		maxIdx = max(maxIdx, cal(exp));
	}

	for (int i = 0; i < 3; i++) {
		if (oper[i].second) continue;
		oper[i].second = true;
		dfs(exp + oper[i].first);
		oper[i].second = false;
	}

}

// 파싱함수
void convert(string s) {
	int i = 0;
	string num = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '*' || s[i] == '+' || s[i] == '-') {
			ex.push_back(s[i]);
			nums.push_back(stoi(num));
			num.clear();
			num.resize(0);
			continue;
		}
		num.push_back(s[i]);
	}
	nums.push_back(stoi(num));
}

long long solution(string expression) {
	convert(expression);
	for (int i = 0; i < 3; i++) {
		oper[i].second = true;
		dfs(oper[i].first);
		oper[i].second = false;
	}
	long long answer = maxIdx;
	return answer;
}