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

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 수식 최대화

 

 

 

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/67257?language=java 

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

 

 

문제 풀이

 

숫자, 연산자들을 배열에 각각 나누어 넣는다.

재귀함수를 활용하여 순열로 연산자 우선순위를 구한다.

Math.abs() 를 사용하여 절대값 구한다.

 

 

이번 문제는 내가 여태까지 푼 문제중 가장 오래 걸렸다. 총 2일이 걸렸는데 첫날에는 코드를 작성하지않고 어떻게 구현할까 고민하는데 하루를 보냈다. 물론 2일 내내 한 것은 아니고 하루에 2,3시간 정도씩은 본 것 같다. 

연산자가 많아봐야 3개기 때문에 일일히 경우의 수를 써서 풀 수 도 있었지만 효율성을 위해서 연산자가 늘어나더라도 적용되는 코드를 만들고 싶어서 고민을 많이했다. 우선 연산자 순위의 경우에 수는 팩토리얼(n!) 이므로 재귀함수를 사용하여 순열을 구했다. 사실 순열알고리즘을 알지 못했어서 직접 만들어보려고 1,2시간은 끙끙댔다. 그러다 결국 구글에 순열알고리즘을 찾았고 그걸 보고 공부한 후 만들어보았다. 순열 알고리즘을 알고나니 손쉽게 풀 수 있었다.

경우의 수를 구한 후, 계산하는 과정에서 처음엔 replace()를 활용하여 풀려고 생각했다. 그러나 생각보다 복잡할 것 같아서 생각을 바꿨다. 처음 문자열들을 숫자와, 연산자로 나눠서 리스트에 저장해두고 필요한 인덱스 별로 꺼내와 계산하는 방식으로 풀었다.

너무 긴 코드여서 안좋은 코드라 생각했는데 다른사람들 풀이를 보니까 나랑 비슷했다. 이렇게 푸는게 맞는거인것 같다. 이틀을 고민한 탓인지 점수는 5점이였다.

 

static int size = 0;
	static String[] equation_arr;
	static ArrayList<ArrayList<String>> result_arr = new ArrayList();
	static ArrayList<String> equList = new ArrayList();
	static ArrayList<Long> numList = new ArrayList();
	static Long max = (long) 0;

public static long solution(String expression) {
	ArrayList<String> equation = new ArrayList();

	if(expression.contains("*")) {
		equation.add("*");
	} 
	if(expression.contains("-")) {
		equation.add("-");
	}
	if(expression.contains("+")) {
		equation.add("+");
	}

	String n = "";
	for(int i = 0; i < expression.length(); i++) {
		char cha = expression.charAt(i);
		if(cha == '*' || cha == '+' || cha == '-') {
			equList.add(cha + "");
			numList.add(Long.parseLong(n));
			n = "";
		}else {
			n += cha;
		}
	}
	numList.add(Long.parseLong(n));

	size = equation.size();
	equation_arr = new String[size];
	boolean[] check = new boolean[size];
	permutation(size, equation, check, equation_arr, 0);



	return max;
}

public static void permutation(int size, ArrayList<String> equation, boolean[] check, String[] equation_arr, int depth) {
	if(depth == size) {
		solve();
		return;
	}

	for (int i = 0; i < size; i++){
		if (!check[i]) {
			check[i] = true; 
			equation_arr[depth] = equation.get(i);
			permutation(size, equation, check, equation_arr, depth+1);
			check[i] = false;
		}
	}
}

public static void solve() {
	ArrayList<String> equ = new ArrayList<>();
	equ.addAll(equList);
	ArrayList<Long> num = new ArrayList<>();
	num.addAll(numList);

	for(int i = 0; i<equation_arr.length; i++) {
		String first = equation_arr[i];
		for(int j = 0; j < equ.size(); j++) {
			if(first.equals(equ.get(j))) {
				long num1 = num.get(j);
				long num2 = num.get(j+1);

				equ.remove(j);
				num.remove(j+1);
				num.remove(j);
				num.add(j, cal(first, num1, num2));

				j--;
			}
		}
	}

	if(Math.abs(num.get(0)) > max) {
		max = Math.abs(num.get(0));

	}

}

public static long cal(String first, long num1, long num2) {
	switch (first) {
	case "*":
		return num1 * num2;
	case "+":
		return num1 + num2;
	case "-":
		return num1 - num2;
	}
	return 0;
}