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

 

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

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

주어진 연산자들의 모든 가능한 우선순위를 계산한 값이 최대인 값을 출력한다.

연산자의 종류는 +,-,* 로만 이루어져 있으므로 연산자들의 우선수위의 경우의수가 총 6가지이다.

6가지의 경우의 수를 모두 구해 놓고 각각의 경우마다 우선순위를 고려하여 수식을 계산했다.

문제에서 친절하게 long 자료형을 쓰라고도 알려주고 있다.

• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.

풀이 방법

1. 연산자 우선수위의 모든 경우를 구한다.
2. 각 경우 마다 우선순위를 고려하여 수식을 계산한다.

수식 계산 방법

1. 수식을 구분자로 분리 (구분자 : +,-,*)

String[] ex_nums = tmp_exp.split("-|\\+|\\*"); // 숫자 분리

2. 수식에서 연산자들을 따로 뽑아서 배열에 저장. 연산자는 늘 숫자의 개수보다 1개 적은 값이 나온다.

    char[] ex_ops = new char[ex_nums.length - 1];
    for (int i = 0, j = 0; j < ex_ops.length; i++) { // 수식의 연산자들 순서대로 뽑기
    if (tmp_exp.charAt(i) == '+' || tmp_exp.charAt(i) == '*' || tmp_exp.charAt(i) == '-') {
            ex_ops[j] = tmp_exp.charAt(i);
                j++;
    }
   }

3. 숫자와 연산자들을 각각 deque에 넣는다. 숫자는 문자열이므로 long으로 변환해서 넣는다.
   계산중인 수식이 "-100 * -200 " 이라면 문자열을 분리 했을 때 {"","100","","200"}으로 분리가된다.
   공백 문자열("")이 나왔다는 것은 음수라는 의미이므로 -1을 곱해 음수 처리 해준다.

                for (int i = 0, j = 0; i < ex_nums.length; i++, j++) {
                    if(ex_nums[i].equals("")) {
                        nums.addLast(Long.parseLong(ex_nums[++i])*-1);
                        j++;
                    }else {
                        nums.addLast(Long.parseLong(ex_nums[i]));
                    }
                    if (j < ex_ops.length)
                        op.addLast(ex_ops[j]);
                }

4. 우선순위에 맞는 연산자라면 계산, 아니라면 그대로 수식에 추가 하는 과정을 반복하여 새로운 수식 생성.
5. 수식에 숫자가 1개 남을 때 까지 위 과정을 반복한다.
6. 숫자가 1개라면 해당 값이 최종 결과 값이므로 숫자로 변환 해 절댓값을 취한다. max값 보다 크면 갱신한다.

전체 코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
class Solution {
  	static char[] ops = { '*', '+', '-' };
	static List<Character[]> orders = new ArrayList<>();
	static Character[] order = new Character[3];
	static boolean[] visited = new boolean[3];
	static long max = Long.MIN_VALUE;
	static String tmp_exp;

	public static long solution(String expression) {
		long answer = 0;
	
		make_orders(0); //수식의 모든 경우를 생성 (순열)

		for (Character[] or : orders) {
			tmp_exp = expression;
		
			long tmp_res = 0;
			for(int now=0;now<3;now++) {
			
				Deque<Long> nums = new ArrayDeque<>();
				Deque<Character> op = new ArrayDeque<>();
				String[] ex_nums = tmp_exp.split("-|\\+|\\*"); // 숫자 분리
				if(ex_nums.length==1) break;
				char[] ex_ops = new char[ex_nums.length - 1];
				for (int i = 0, j = 0; j < ex_ops.length; i++) { // 수식의 연산자들 순서대로 뽑기
					if (tmp_exp.charAt(i) == '+' || tmp_exp.charAt(i) == '*' || tmp_exp.charAt(i) == '-') {
						ex_ops[j] = tmp_exp.charAt(i);
						j++;
					}
				}
				for (int i = 0, j = 0; i < ex_nums.length; i++, j++) {
					if(ex_nums[i].equals("")) {
						nums.addLast(Long.parseLong(ex_nums[++i])*-1);
						j++;
					}else {
						nums.addLast(Long.parseLong(ex_nums[i]));
					}
					if (j < ex_ops.length)
						op.addLast(ex_ops[j]);
				}
				
			
				String tmp = "";
				while (!op.isEmpty()) {
					char this_op = op.pollFirst();
					if (this_op == or[now]) {
						long cal_res=cal(this_op, nums.pollFirst(), nums.pollFirst());
						nums.addFirst(cal_res);
					}else {
						tmp+=nums.pollFirst();
						tmp+=this_op;
					}
				}
				while(!nums.isEmpty()) {
					tmp+=nums.pollFirst();
				}
				tmp_exp= tmp;
			}
			tmp_res = Math.abs(Long.parseLong(tmp_exp));
			max=Math.max(max, tmp_res);

		}
		answer=max;
		return answer;
	}

	private static Long cal(char op, Long a, Long b) {
		if (op == '+')
			return a + b;
		else if (op == '*')
			return a * b;
		else
			return a - b;
	}

	private static void make_orders(int cnt) {
		if (cnt == 3) {
			orders.add(Arrays.copyOf(order, 3));

			return;

		}
		for (int i = 0; i < 3; i++) {
			if (visited[i])
				continue;
			order[cnt] = ops[i];
			visited[i] = true;
			make_orders(cnt + 1);
			visited[i] = false;

		}

	}
}