[카카오 인턴] 수식 최대화 (DFS, Java, 프로그래머스)

 

 

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    static char[] prior = {'+', '-', '*'};
    static boolean[] check = new boolean[3];
    static List<Long> nums = new ArrayList<>();
    static List<Character> ops = new ArrayList<>();
    static long answer;
    
    static void dfs(int count, char[] perm) {
        if (count == 3) {
            var copyNums = new ArrayList<>(nums);
            var copyOps = new ArrayList<>(ops);
            
            //연산자가 우선순위에 따라 담겨있는 배열 perm
            for (var i = 0; i < perm.length; i++) {
                for (var j = 0; j < copyOps.size(); j++) {
                    if (perm[i] == copyOps.get(j)) {
                        //우선순위에 맞는 연산자를 찾으면 연산자의 앞뒤의 숫자를 꺼내서 계산 후 다시 넣기
                        var result = calc(copyNums.remove(j), copyNums.remove(j), perm[i]);
                        copyNums.add(j, result);
                        //해당 위치의 연산자 제거
                        copyOps.remove(j);
                        //2개를 꺼내고 1개를 넣었으므로 j는 --;
                        j--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(copyNums.get(0)));
            return;
        }
        //연산자에 대한 모든 경우의 수 생성
        for (int i = 0; i < 3; i++) {
            if (check[i]) continue;
            
            check[i] = true;
            perm[count] = prior[i];
            dfs(count + 1, perm);
            check[i] = false;
        }
    }
    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 long solution(String expression) {
        answer = 0;
        
        // 1. String을 숫자와 연산자로 나눠 각각 배열에 저장.        
        nums = Arrays.stream(expression.split("[\\+\\-\\*]")).map(Long::parseLong).collect(Collectors.toList());
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') 
                ops.add(expression.charAt(i));
        }
        
        dfs(0, new char[3]);
        
        return answer;
    }
}