수식최대화 : 문자열 (Level 2)

이번문제는 생각보다 한번에 해결책이 떠오르지 않아 조금 오래걸렸던 문제입니다.

 

딱히 효율적인 방안이 떠오르지 않고, 경우의 수가 6개 밖에 되지 않아 전부 다 계산하는 방법을 선택했습니다.

 

[설명]

1. 해당 수식을 숫자와 연산자를 각각 리스트에 담는다. 
2. 6가지 경우 수에 따라 연산자 우선순위대로 계산을 진행한다.
   1. 이때, 연산은 List에서 직접 수행한다.
   2. 연산자가 나오면 앞뒤로 계산을 수행 후, 연산에 관여된 3개의 데이터를 삭제 한다.
   3. 이때, 리스트삭제로 인해 index가 변경되니, 주의하자. -> (i-1)위치 3번삭제 후 -> i--적용
3. 한번의 경우의 수가 끝나면, 절댓값 적용 후 다른 경우의 값보다 크면 업데이트한다.
   1. 주의, 결과값을 long형으로 타입을 변경해 주어야한다. 

 

import java.util.*;

class Solution {
	public long solution(String expression) {
		long answer = -999999;

		List<String> list = new ArrayList<String>();

		int fIndex = 0; // 숫자 시작위치 인덱스

		// 식을 숫자/연산자 나눠서 List에 add
		for (int i = 0; i < expression.length(); i++) {
			// 연산자라면 (자르기***)
			if ((String.valueOf(expression.charAt(i))).equals("*") || (String.valueOf(expression.charAt(i))).equals("+")
					|| (String.valueOf(expression.charAt(i))).equals("-")) {
				list.add(expression.substring(fIndex, i)); // 연산자 전까지의 숫자만 넣기***
				list.add(expression.substring(i, i + 1)); // 연산자 넣기
				fIndex = i + 1; // 숫자 시작인덱스 연산자 뒤로 이동
			}

			if (i == expression.length() - 1) { // 마지막은 연산자 없음
				list.add(expression.substring(fIndex, expression.length()));
			}
		}

		String[][] cArr = { { "*", "+", "-" }, { "*", "-", "+" }, { "+", "*", "-" }, { "+", "-", "*" },
				{ "-", "+", "*" }, { "-", "*", "+" } };

		for (int a = 0; a < 6; a++) { // 우선순위 경우의 수
			String[] arr = cArr[a];
			List<String> tmpList = new ArrayList<String>();
			tmpList.addAll(list); // 깊은복사***

			for (int c = 0; c < 3; c++) { // 각 연산자별 비교
				String cal = arr[c];

				for (int i = 0; i < tmpList.size(); i++) { // 전부 돌면서 계산
					long value = 0;
					if (tmpList.get(i).equals(cal)) {
						long left = Long.parseLong(tmpList.get(i - 1));
						long right = Long.parseLong(tmpList.get(i + 1));

						if (cal.equals("*")) {
							value = left * right;
						} else if (cal.equals("-")) {
							value = left - right;
						} else if (cal.equals("+")) {
							value = left + right;
						}

						tmpList.remove(i - 1); // 계산된 값 제거
						tmpList.remove(i - 1);
						tmpList.remove(i - 1);

						tmpList.add(i - 1, String.valueOf(value)); // 리스트 중간값 삽입***
						i--; // 앞쪽부터 다시 확인
					}
				}
			}
			answer = Math.max(answer, Math.abs(Long.parseLong(tmpList.get(0)))); // 절댓값 (큰값 넣기)
		}
		return answer;
	}
}