[Java]Programmers 수식 최대화(2020 KAKAO Internship)

import java.util.*;

class Solution {

    long answer = 0;
    List<String> exps = new ArrayList<>();

    public long solution(String expression) {
        parse(expression);
        dfs(new char[3], 0, new boolean[4]);
        return answer;
    }

    // 주어진 문자열에서 숫자와 연산자 분리
    void parse(String e) {
        StringBuilder sb = new StringBuilder();
        for (char c : e.toCharArray()) {
            if (c - '0' < 0) {
                exps.add(sb.toString());
                exps.add(new String(new char[]{c}));
                sb = new StringBuilder();
            } else {
                sb.append(c);
            }
        }
        exps.add(sb.toString());
    }

    // 연산자 순열 구하기(3! = 6)
    char[] exp = {'+', '-', '*'};

    void dfs(char[] priority, int now, boolean[] isAdded) {
        if (now == 3) {
            answer = Math.max(answer, calculate(priority));
            return;
        }

        for (char c : exp) {
            if (isAdded[c - '*']) continue;
            isAdded[c - '*'] = true;
            priority[now] = c;
            dfs(priority, now + 1, isAdded);
            isAdded[c - '*'] = false;
        }
    }

    // 숫자 계산
    long calculate(char[] priority) {
        Deque<String> q = infixToPostfix(priority);

        // 숫자들을 임시 저장할 스택
        Stack<Long> temp2 = new Stack<>();
        while (!q.isEmpty()) {
            String e = q.poll();

            // 연산자일 경우 스택에서 2개를 꺼내서 계산 후 결과값 스택으로 이동
            if (e.equals("*") || e.equals("+") || e.equals("-")) {
                long i2 = temp2.pop();
                long i1 = temp2.pop();
                temp2.push(calc(e, i1, i2));

            } else {
                // 숫자는 바로 스택으로 이동
                temp2.push(Long.parseLong(e));
            }
        }

        return Math.abs(temp2.pop());
    }

    // 중위 표기 -> 후위표기 변환
    Deque<String> infixToPostfix(char[] priority) {
        Deque<String> q = new ArrayDeque<>();
        Stack<String> temp = new Stack<>();
        for (String e : exps) {
            if (e.equals("*") || e.equals("+") || e.equals("-")) {

                // 현재 숫자보다 우선순위가 크거나 같은 연산자들을 모두 스택에서 큐로 이동
                while (!temp.isEmpty() && getPriority(priority, temp.peek()) >= getPriority(priority, e)) {
                    q.offer(temp.pop());
                }

                // 현재 연산자 스택에 보관
                temp.push(e);
            } else {

                // 숫자는 바로 큐에 넣기
                q.offer(e);
            }
        }

        // 연산자가 스택에 남아있다면 큐로 이동
        while (!temp.isEmpty()) q.offer(temp.pop());
        return q;
    }

    // 문자열인 계산식과 숫자들을 받아서 계산
    long calc(String c, long i1, long i2) {
        switch (c.charAt(0)) {
            case '+': {
                return i1 + i2;
            }
            case '-': {
                return i1 - i2;
            }
            case '*': {
                return i1 * i2;
            }
        }
        throw new RuntimeException();
    }

    // 우선순위 배열로부터 우선순위 가져옴
    int getPriority(char[] priority, String now) {
        for (int i = 0; i < 3; i++) {
            if (priority[i] == now.charAt(0)) return i;
        }
        return -1;
    }

}