[pro] 프로그래머스 level2 67257 수식 최대화 (Java) - 브루트포스, dfs

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

 

[풀이]

먼저 피연산자와 연산자를 분리해서 List에 넣은 후, 모든 연산자의 우선순위 순열에 대해 값을 계산해준다. 

 

+, *, -  3가지 연산자에 대해서 가능한 우선순위는 3!=6가지이다. dfs를 통해 이에 대한 순열을 구할 수 있다.

그 후 연산자 우선순위에 따라서 계산해준 후 최대값을 비교해서 얻어낸다.

 

[코드]

 

import java.util.*;

class Solution {
    static long answer = 0;
    static String op[] = {"+","-","*"};
    static boolean[] visited = new boolean[3];
    static ArrayList<Long> numList = new ArrayList<>();
    static ArrayList<String> opList = new ArrayList<>();
    static String[] perm = new String[3];
    
    public long solution(String expression) {
        String num = "";
        
        //op, num 구분
        for(int i=0; i<expression.length(); i++){
            char c = expression.charAt(i);
            if(c=='*' || c=='+' || c=='-'){
                opList.add(c+""); 
                numList.add(Long.parseLong(num));
                num = "";
            }
            else{
                num += c;
            }
        }
        //마지막 숫자
        numList.add(Long.parseLong(num));
        
        //순열 만들기
        makePermutation(0);
        
        return answer;
    }
    
    static void makePermutation(int depth){
        if(depth==op.length){
            //3개를 선택함 -> 연산
            sol();
            return;
        }
        
        for(int i=0; i<op.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            perm[depth] = op[i];
            makePermutation(depth+1);
            visited[i] = false;
        }
    }
    
    static void sol(){
        //list 복사
        ArrayList<String> oper = new ArrayList<String>();
        oper.addAll(opList);
        
        ArrayList<Long> num = new ArrayList<Long>();
        num.addAll(numList);
        
        //연산자 우선순위에 따라 계산
        for(int i=0; i<perm.length; i++){
            String op = perm[i];
            for(int j=0; j<oper.size(); j++){
                if(oper.get(j).equals(op)){
                    long n1 = num.get(j);
                    long n2 = num.get(j+1);
                    long res = cal(n1, n2, op);
                    
                    //list 갱신
                    num.remove(j+1);
                    num.remove(j);
                    oper.remove(j);
                    
                    num.add(j, res);
                    
                    j--;
                }
            }
        }
        
        answer = Math.max(answer, Math.abs(num.get(0)));
    }
    
    static long cal(long n1, long n2, String op){
        long res = 0;
        switch(op){
            case "*": 
                res = n1 * n2;
                break;
            case "+":
                res = n1 + n2;
                break;
            case "-":
                res = n1 - n2;
                break;
        }
        
        return res;
    }
}