[Programmers] 수식 최대화

// 1. arraylist[num]
// 2. arraylist[cal]
// 3. 6번 진행
// 4. cal first -> a[0] = a[0] + a[1]
// 4.1 연산한 수에는 none을 넣어 연산이 완료되었음을 입력
// 4.2 num.size는 cal.size+1이고 cal[index] 연산시 num[cal.index+1]은 반드시 숫자임
// 5. num[cal.index+1]과 none이 아닌 수를 앞에서 while을 통해 찾아 연산

import java.util.ArrayList;

class Solution {
    static boolean[] calculate = new boolean[3]; // + - *
    static ArrayList<String> numList;
    static ArrayList<String> calList;
    static long answer;
    public long solution(String expression) {
        answer = 0;
        numList = new ArrayList<>();
        calList = new ArrayList<>();
        int left = 0;
        // 수와 연산 List에 저장
        for(int i = 1; i < expression.length(); i++){
            int tmp = expression.charAt(i) - '0';
            if(tmp < 0 || tmp > 9){
                numList.add(expression.substring(left, i));
                calList.add(expression.substring(i, i+1));
                left = i+1;
            }
        }
        numList.add(expression.substring(left, expression.length()));
        String[] list = numList.toArray(new String[numList.size()]);
        bf(list, 0);
        return answer;
    }
    // 재귀를 통해 + - * 의 모든경우 탐색
    void bf(String[] list, int depth){
        if(depth == 3){
            if(answer < Math.abs(Long.valueOf(list[0]))){
                answer = Math.abs(Long.valueOf(list[0]));
            }
        }else{
            for(int i = 0; i < 3; i++){
                if(!calculate[i]){
                    calculate[i] = true;
                    bf(cal(list, i), depth+1);
                    calculate[i] = false;
                }
            }
        }
    }
    // 연산자 입력에 따른 연산 
    public String[] cal(String[] list, int calIndex){
        String[] tmpList = new String[list.length];
        for(int i = 0; i < list.length; i++){
            tmpList[i] = list[i];
        }
        switch(calIndex){
            case 0:{
                for(int i = 0; i < calList.size(); i++){
                    if(calList.get(i).equals("+")){
                        int index = i;
                        while(true){
                            if(tmpList[index].equals("none")){
      index--;                          
                            }else{
                                break;
                            }
                        }
                        tmpList[index] = String.valueOf(Long.valueOf(tmpList[index])+Long.valueOf(tmpList[i+1]));
                        tmpList[i+1] = "none";
                    }
                }
                break;
            }
            case 1:{
                for(int i = 0; i < calList.size(); i++){
                    if(calList.get(i).equals("-")){
                        int index = i;
                        while(true){
                            if(tmpList[index].equals("none")){
      index--;                          
                            }else{
                                break;
                            }
                        }
                        tmpList[index] = String.valueOf(Long.valueOf(tmpList[index])-Long.valueOf(tmpList[i+1]));
                        tmpList[i+1] = "none";
                    }
                }
                break;
            }
            case 2:{
                for(int i = 0; i < calList.size(); i++){
                    if(calList.get(i).equals("*")){
                        int index = i;
                        while(true){
                            if(tmpList[index].equals("none")){
      index--;                          
                            }else{
                                break;
                            }
                        }
                        tmpList[index] = String.valueOf(Long.valueOf(tmpList[index])*Long.valueOf(tmpList[i+1]));
                        tmpList[i+1] = "none";
                    }
                }
                break;
            }
            default: {
                break;
            }
        }
        return tmpList;
    }
}

카카오 1번 쯤 되는듯하다. 어렵진안았는데 시간효율적 측면에서 느린것같다.