[lv2] 수식 최대화

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

 

1. 입력 문자열 expression으로 부터, 수와 연산자를 파싱해 list에 저장한다.

 

2. 연산자 우선순위 배열을 하드코딩한다.

경우의 수는 3! = 6개로, 순열로 뽑는 것 보다 나은 방법이었다.

 

3. 재귀로 각 경우의 값을 구한다.

nums[i] 와 nums[i+1]를 opers[i]로 연산하여 다시 nums[i]에 집어넣는다.

결국엔 opers.size() == 0일 때, nums.get(0)이 최종 연산 값이 된다.

 

항상 연산자의 개수는 수의 개수 -1임이 보장되므로, 인덱스 처리만 유의하면 오류가 나지 않는다.

 

4. 모든 값 중 절댓값이 최대인 경우를 출력한다.

 

+ StringBuilder는 clear() 함수를 지원하지 않는다.

대안으로,

1. sb = new StringBuilder();

2. sb.delete(0, sb.length());

3. sb.setLength(0);

등이 있다.

 

3번이 제일 빠르다고 한다.

 

import java.util.*;

class Solution {

	long answer;
	List<Long> nums = new ArrayList<>();
	List<Character> opers = new ArrayList<>();
	String[] expressArr = {"*+-", "*-+", "-+*", "-*+", "+*-", "+-*"};
	String expression;

	<T> List<T> deepCopy(List<T> origin) {
		List<T> copy = new ArrayList<>();

		for(T t : origin)
			copy.add(t);

		return copy;
	}

	void solve(List<Long> nums, List<Character> opers, String express, int expressIdx) {

		if(expressIdx == 3) {
			answer = Math.max(answer, Math.abs(nums.get(0)));
			return;
		}

		char oper = express.charAt(expressIdx);

		int O = opers.size();

		for(int i=0; i<O; i++) {
			if(opers.get(i) == oper) {
				long value = 0;

				if(oper == '*')
					value = nums.get(i) * nums.get(i+1);
				else if(oper == '+')
					value = nums.get(i) + nums.get(i+1);
				else if(oper == '-')
					value = nums.get(i) - nums.get(i+1);

				nums.remove(i+1);
				nums.set(i, value);
				
				opers.remove(i);

				O--;
				i--;
			}
		}

		solve(nums, opers, express, expressIdx + 1);
	}


	void init() {
		StringBuilder sb = new StringBuilder();

		for(int i=0; i<expression.length(); i++) {

			char c = expression.charAt(i);

			if(Character.isDigit(c))
				sb.append(c);
			else {
				nums.add(Long.parseLong(sb.toString()));
				sb.delete(0, sb.length());

				opers.add(c);
			}
		}
		nums.add(Long.parseLong(sb.toString()));
	}

	public long solution(String expression) {
		this.expression = expression;
		init();

		for(int i=0; i<6; i++)
			solve(deepCopy(nums), deepCopy(opers), expressArr[i], 0);

		return answer;
	}
}