[java] 프로그래머스 - 수식 최대화

문제

프로그래머스-수식 최대화
입력받은 연산수식에서 연산자(-,+,*)의 우선순위를 재정의하여 나온 식의 최대값을 구하는 문제.
음수가 나온 경우, 절댓값으로 반환하여 계산한다

• 제한 사항
  expression : 연산 수식이 담긴 문자열
  expression은 길이가 3이상 100이하
  expression은 공백, 괄호없이 숫자와 +,-,*로 이루어져있다
  expression은 적어도 1개이상 연산자를 포함하고 있다
  잘못된 연산식은 주어지지 않는다
  같은 연산자끼리는 앞의 숫자가 우선순위가 높다

• 예시
  expression : 100-200*300-500+20
  연산자 우선순위를 *>+>-로 정의한 경우 가장 큰 절댓값을 얻을 수 있다
  1) 100-(200*300)-500+20
  2) 100-60000-(500+20)
  3) (100-60000)-520
  4) (-59900-520)
  5) -60420

풀이

주어지는 연산자는 3개이므로 3개의 우선순위는 2!=6개다
우선순위는 6개이므로 미리 정의해서 사용한다
우선 숫자와 연산자를 분리한 후, 6개의 우선순위를 하나씩 계산한다

• - > + > *의 경우
  주어진 연산식이 5 + 3 - 2 * 6 이라고 할때 숫자와 연산자를 분리한다

  숫자 : 5, 3, 2, 6  
  연산자 : +, -, *  
  

  먼저 연산자에서 우선순위가 제일 앞선 -를 찾는다
  -의 인덱스 j는 1이다
  숫자에서 j번째와 j+1번째를 제거한 다음, -로 계산해서 j번째로 교체한다

즉, 1번째인 3, 2번째 2를 제거하고, 3-2를 1번째에 다시 넣는다
계산이 끝난 연산자 -는 연산자 목록에서 제거하고 남은 연산자 중에 현재 우선순위인 -를 찾아 반복수행한다

숫자 : 5, 6, 6  
연산자 : +, *  

다음 연산자 우선순위인 +로 진행한다

숫자 : 11, 6
연산자 : *

*의 계산을 진행한다

숫자 : 66
연산자 : 

남은 숫자가 해당 우선순위에 따른 값이된다

소스코드

import java.util.*;
class Solution {
	static long[] n; // 연산식에서 뽑은 숫자들이 들어갈 배열
	static ArrayList<Character> oper; // 연산식에서 뽑은 연산자들이 들어갈 어레이리스트
	// 미리 정의한 3개 연산자의 우선순위
	static int[][] operPr = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } };
	static Map<Character, Integer> map; // 연산자와 인덱스를 연결시켜줄 맵

	public long solution(String str) {
		oper = new ArrayList<>();
		// operPr에서 0번째의 값은 -의 우선순위, 1번째값은 +의 우선순위를 의미함
		map = new HashMap<>();
		map.put('-', 0);
		map.put('+', 1);
		map.put('*', 2);

		char[] c = str.toCharArray();
		// 연산식을 돌면서 연산자인 경우 숫자분리를 위해 ' '로 바꿔주고, 연산자는 따로 저장한다
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < c.length; i++) {
			if (c[i] == '+') {
				c[i] = ' ';
				oper.add('+');
			} else if (c[i] == '-') {
				c[i] = ' ';
				oper.add('-');
			} else if (c[i] == '*') {
				c[i] = ' ';
				oper.add('*');
			}
			sb.append(c[i]);
		}
		
		// 5 3 2 6 으로 연산자가 제외된 문자열을 잘라서 숫자로 변환
		String[] nums = sb.toString().split(" ");
		n = new long[nums.length];
		for (int i = 0; i < nums.length; i++) {
			n[i] = Integer.parseInt(nums[i]);
		}


		// 연산자 우선순위
		long answer = 0;
		for (int i = 0; i < operPr.length; i++) {
			// openPr[i] 이 현재 연산자 우선순위
			long result = Math.abs(getValue(operPr[i])); // 계산 결과의 절댓값을 취함
			answer = Math.max(answer, result);

		}
		return answer;
	}

// 해당 연산자의 우선순위 대로 식을 계산하는 메서드
	private long getValue(int[] ops) {
		ArrayList<Long> number = new ArrayList<>();
		ArrayList<Character> opers = new ArrayList<>();

		for (int i = 0; i < oper.size(); i++) {
			opers.add(oper.get(i));
		}
		for (int i = 0; i < n.length; i++) {
			number.add(n[i]);
		}

		for (int i = 2; i > -1; i--) { // 우선순위가 2부터 0으로
			for (int j = 0; j < opers.size(); j++) {
				if (ops[map.get(opers.get(j))] == i) { // 만일 해당차례의 연산자가 우선순위가 i라면
					long a = number.remove(j); // 숫자 2개 뽑아서
					long b = number.remove(j);
					long result = doOperation(opers.get(j), a, b); // 연산
					number.add(j, result); // 다시 더해주고
					opers.remove(j); // 완료한 연산자는 제거
					j--; // 제거했으므로 인덱스 하나 땡겨짐
				}
			}
		}
		return number.remove(0); // 연산 수행 후 남은 숫자 (해당 우선순위에 따른 연산 답)
	}

	private long doOperation(char op, long a, long b) {
		switch (op) {
		case '+':
			return a + b;
		case '-':
			return a - b;
		case '*':
			return a * b;
		}
		return 0;
	}

}