[프로그래머스] 수식 최대화

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67257?language=java

프로그래머스

---

문제 풀이

1. 연산자 우선순위 순열을 생성한다. -> 총 6가지의 경우의 수가 나옴

: permute() 함수

 

2. 각 순열의 우선순위에 맞춰 expression을 계산한다.

: calculate() 함수

 

3. 계산해서 나온 결과 값들의 절대값들 중, 최대의 값을 출력한다.

 

import java.util.*;

class Solution {
    
    static char[] ops = {'+', '-', '*'}; // 연산자 배열
    static boolean[] visited = new boolean[ops.length];
    static char[] result = new char[ops.length];
    static List<char[]> permuteList = new ArrayList<>();
    
    public long solution(String expression) {
        long answer = 0;
        
        // 1. 연산자 우선순위 경우의 수를 가진 순열 구하기
        permute(0);
        
        // 2. 해당 연산자에 따라 계산하기
        for(char[] permute : permuteList) {
            
            // 2.1 expression을 연산자와 숫자로 분리
            List<Long> numList = new ArrayList<>();
            List<Character> opsList = new ArrayList<>(); 
            StringBuilder sb = new StringBuilder();

            for(int i=0; i<expression.length(); i++) {
                char c = expression.charAt(i);
                
                if(c=='+' || c=='-' || c=='*') {
                    numList.add(Long.parseLong(sb.toString())); // 100과 같은 연속된 숫자가 있을 가능성 고려
                    opsList.add(c);
                    sb.setLength(0); // 초기화!
                } else {
                    sb.append(c);
                }
            }
            
            numList.add(Long.parseLong(sb.toString())); // 마지막 남은 숫자 추가     
            
            long temp = calculate(numList, opsList, permute);
            answer = Math.max(answer, temp);
            
        }
        return answer;
    }
    
    static void permute(int depth) {
        if(depth == ops.length) {
            permuteList.add(result.clone());
        }
        
        for(int i=0; i<ops.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[depth] = ops[i];
                permute(depth + 1);
                visited[i] = false;
            }
        }
    }
    
    static long calculate(List<Long> nums, List<Character> ops, char[] permute) {
       List<Long> numList = new ArrayList<>(nums);
       List<Character> opsList = new ArrayList<>(ops);

        for(char op : permute) {
            int i = 0;
            while(i < opsList.size()) {
                if(opsList.get(i) == op) {
                    long a = numList.get(i);
                    long b = numList.get(i+1);
                    long res = 0;
                    
                    switch(op) {
                        case '+': res = a + b; break;
                        case '-': res = a - b; break;
                        case '*': res = a * b; break;
                    }
                    
                    numList.set(i, res);
                    numList.remove(i+1);
                    opsList.remove(i);
                    
                } else {
                    i++;
                }
            }
        }
        return Math.abs(numList.get(0));
    }
}