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

수식 최대화

• 한 번에 로직을 떠올리기 쉽지 않은 어려운 문제,,,,
• 일단 주어진 식의 정수값과 연산자를 구분지어 ArrayList에 저장한다.
• 만들어낼 수 있는 연산자 조합을 char[] 배열로 만들어내고, 조합이 만들어질 때마다 그 연산 값을 구해 answer에 넣고 Math.max()로 최댓값을 유지시킨다.
• cal()함수로 연산자에 따른 연산을 진행시키는데, 이때 두 값을 넘겨줄 때, ArrayList를 이용해 cNums.remove(j) 두 번을 시켜서 연산자의 좌우 값을 넘겨준다. 계산값을 그 자리에 다시 add(j,res)시킨다. cOps에서도 계산한 연산자를 remove(j)시키고, 전체적으로 ArrayList의 크기가 하나 줄었으므로 j—를 해준다.
• 나중에 다시 한 번 풀어보자..!

import java.util.ArrayList;

public class MaxExpression {
    static char[] prior = {'+', '-', '*'};
    static boolean[] check = new boolean[3];
    static ArrayList<Long> nums = new ArrayList<Long>();
    static ArrayList<Character> ops = new ArrayList<Character>();
    static long answer;

    public long solution(String expression) {
        answer = 0;

        String num="";
        for(int i=0;i<expression.length();i++){
            if(expression.charAt(i) >= '0' && expression.charAt(i) <= '9'){
                num += expression.charAt(i);
            }else{
                nums.add(Long.parseLong(num));
                num = "";
                ops.add(expression.charAt(i));
            }
        }
        nums.add(Long.parseLong(num));
        dfs(0, new char[3]);

        return answer;
    }

    public static Long calc(Long num1, Long num2, char op){
        long num = 0;
        switch (op){
            case '+' : {
                return num1 + num2;
            }
            case '-' : {
                return num1 - num2;
            }
            case '*' : {
                return num1 * num2;
            }
        }
        return num;
    }

    public static void dfs(int count, char[] p){
        if(count == 3){
            ArrayList<Long> cNums = new ArrayList<>(nums);
            ArrayList<Character> cOps = new ArrayList<Character>(ops);

            for(int i=0;i<p.length;i++){
                for(int j=0; j< cOps.size(); j++){
                    if(p[i] == cOps.get(j)){
                        Long res = calc(cNums.remove(j), cNums.remove(j), p[i]);
                        cNums.add(j, res);
                        cOps.remove(j);
                        j--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(cNums.get(0)));
            return;

        }

        for(int i=0; i< 3; i++){
            if(!check[i]){
                check[i] = true;
                p[count] = prior[i];
                dfs(count+1,p);
                check[i] = false;
            }
        }
    }
}