[Programmers] 수식 최대화

2020 카카오 인턴 2번 문제였다.

수식의 연산자에 대해 우선순위를 부여하고 그순간에서의 최대값을 구하는 문제였다. 주어진 연산자가 3개였으므로 순열을 이용하여 모든 경우의 수를 보았다. 그리고 수식의 전부를 token화 시켜서 List의 형태로 저장하였고, 계산을 할땐 list에서 remove해주는 방식으로 해주었다. 여기서 주의할점은 for문안에서 List의 사이즈를 건들수 있는 remove연산을 해주었기 때문에 index값을 조정해주는 것이 꼭필요했다.

package programmers;
 
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_2020카카오인턴_수식최대화 {
    static String[] flags = {"*","+","-"};
    static List<String> exp;
    static List<String> temp;
    static String[] pick;
    static boolean[] visit;
    static long answer;
    
    public static void main(String[] args) {
        String expression="100-200*300-500+20";
        System.out.println(solution(expression));
    }
    
    static long solution(String expression) {
        
 
        StringTokenizer st1 = new StringTokenizer(expression,"*-+");
        StringTokenizer st2 = new StringTokenizer(expression,"0123456789");
        
        exp=new ArrayList<>();
        exp.add(st1.nextToken());
        while(st1.hasMoreTokens()) {
            exp.add(st2.nextToken());
            exp.add(st1.nextToken());
        }
        temp=new ArrayList<>();
        
        pick=new String[3];
        visit=new boolean[3];
        answer=0;
        
        perm(0);
        
        return answer;
    }
    
    static void perm(int depth) {
        if(depth==3) {
            copy();
            calc();
            return;
        }
        
        for(int i=0;i<3;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                pick[depth]=flags[i];
                perm(depth+1);
                visit[i]=false;
            }
        }
    }
    
    static void calc() {
        
        
        for(int i=0;i<3;i++) {
            String flag=pick[i];
            
            for(int len=0;len<temp.size();len++) {
                if(temp.get(len).equals(flag)) {
                    if(flag.equals("*")) {
                        temp.set(len, (Long.parseLong(temp.get(len-1))*Long.parseLong(temp.get(len+1))) +"");
                        temp.remove(len+1);
                        temp.remove(len-1);
                    }else if(flag.equals("-")) {
                        temp.set(len, (Long.parseLong(temp.get(len-1))-Long.parseLong(temp.get(len+1))) +"");
                        temp.remove(len+1);
                        temp.remove(len-1);
                    }else if(flag.equals("+")) {
                        temp.set(len, (Long.parseLong(temp.get(len-1))+Long.parseLong(temp.get(len+1))) +"");
                        temp.remove(len+1);
                        temp.remove(len-1);
                    }
                    len=len-2;
                }
            }
        }
        
        answer=Math.max(answer, Math.abs(Long.parseLong(temp.get(0))));
    
    }
    
    static void copy() {
        temp.clear();
        for(int i=0;i<exp.size();i++) {
            temp.add(exp.get(i));
        }
    }
}