[JAVA 문제 풀이] 388. 수식 최대화

내가 작성한 코드

import java.util.*;

class Solution {
    public long solution(String expression) {
        long answer = 0;
        String[] tokens = expression.split("(?=[+\\-*])|(?<=[+\\-*])"); // 숫자와 기호 분리
        List<Long> numberList = new ArrayList<>(); // 각 기호 우선순위별 계산 결과를 담을 리스트
        String[][] priority = new String[6][3]; // 기호의 우선순위를 담을 이차원 배열
        List<String> tokenList = new ArrayList<>(Arrays.asList(tokens)); // 배열을 리스트화

        priority[0] = new String[] { "*", "+", "-" };
        priority[1] = new String[] { "*", "-", "+" };
        priority[2] = new String[] { "+", "*", "-" };
        priority[3] = new String[] { "+", "-", "*" };
        priority[4] = new String[] { "-", "+", "*" };
        priority[5] = new String[] { "-", "*", "+" };

        for (int i = 0; i < priority.length; i++) {
            numberList.add(getResult(tokenList, priority[i]));
        }

        return Collections.max(numberList);
    }

    // 우선순위별 계산 결과를 반환하는 함수
    private long getResult(List<String> tokenList, String[] priority) {
        List<String> temp = new ArrayList<>(tokenList);

        calculate(temp, priority[0]);
        calculate(temp, priority[1]);
        calculate(temp, priority[2]);

        return Math.abs(Long.parseLong(temp.get(0)));
    }

    // 기호별로 계산하는 함수
    private void calculate(List<String> tokenList, String symbol) {
        for (int i = 0; i < tokenList.size(); i++) {
            if (tokenList.get(i).equals(symbol)) {
                long cal = 0;
                if (symbol.equals("*")) {
                    cal = Long.parseLong(tokenList.get(i - 1)) * Long.parseLong(tokenList.get(i + 1));
                }

                if (symbol.equals("+")) {
                    cal = Long.parseLong(tokenList.get(i - 1)) + Long.parseLong(tokenList.get(i + 1));
                }

                if (symbol.equals("-")) {
                    cal = Long.parseLong(tokenList.get(i - 1)) - Long.parseLong(tokenList.get(i + 1));
                }

                tokenList.set(i, String.valueOf(cal));
                tokenList.remove(i + 1); // 오른쪽 숫자 제거
                tokenList.remove(i - 1); // 왼쪽 숫자 제거
                i -= 1; // 인덱스 보정
            }
        }
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    public long solution(String expression) {

        // 숫자 부분만 추출 (정규표현식으로 *, -, + 를 기준으로 분리)
        String[] tmps = expression.split("[*,\\-,+]");
        Long[] num = new Long[tmps.length];
        for (int i = 0; i < tmps.length; i++) {
            num[i] = Long.parseLong(tmps[i]); // 숫자 배열로 변환
        }

        // 연산자만 추출해서 배열로 저장
        char[] oper = expression.replaceAll("[0-9]", "").trim().toCharArray();

        // 연산자 우선순위를 저장할 배열
        int[] visit = new int[3]; // 0: *, 1: +, 2: -
        dfs(1, visit, num, oper); // 우선순위 순열 만들기

        return max; // 최대값 반환
    }

    static Long max = 0L; // 최대 절댓값 저장

    // 연산 실행 함수
    static void cal(int[] visit, Long[] num, char[] opers) {
        // 각 연산자에 대한 우선순위 설정
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('*', visit[0]);
        map.put('+', visit[1]);
        map.put('-', visit[2]);

        // 숫자 리스트와 연산자 리스트로 변환
        // LinkedList를 사용하는 이유: 중간 삽입/삭제가 편리
        LinkedList<Long> arr = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            arr.add(num[i]);
        }

        LinkedList<Character> oper = new LinkedList<>();
        for (int i = 0; i < opers.length; i++) {
            oper.add(opers[i]);
        }

        // 우선순위 1, 2, 3 순으로 계산 수행
        for (int i = 1; i <= 3; i++) {
            LinkedList<Long> tmparr = new LinkedList<>(); // 계산 후 새로운 숫자 리스트
            LinkedList<Character> tmpoper = new LinkedList<>(); // 남은 연산자 리스트

            tmparr.add(arr.get(0)); // 첫 숫자 삽입

            int len = oper.size();

            for (int j = 0; j < len; j++) {
                char op = oper.get(j);
                if (map.get(op) == i) {
                    // 현재 연산자가 현재 우선순위에 해당하면 계산 수행
                    Long tmp2 = arr.get(j + 1);
                    Long tmp1 = tmparr.removeLast(); // 마지막 숫자 꺼냄

                    // 연산 수행
                    if (op == '*') {
                        tmparr.add(tmp1 * tmp2);
                    } else if (op == '+') {
                        tmparr.add(tmp1 + tmp2);
                    } else {
                        tmparr.add(tmp1 - tmp2);
                    }
                } else {
                    // 현재 우선순위가 아니면 그대로 추가
                    tmparr.add(arr.get(j + 1));
                    tmpoper.add(oper.get(j));
                }
            }

            // 계산 결과를 다음 단계로 전달
            arr = tmparr;
            oper = tmpoper;
        }

        // 최종 결과 절댓값 비교
        Long tmp = Math.abs(arr.get(0));
        if (max < tmp) {
            max = tmp;
        }
    }

    // 연산자 우선순위 순열 생성 (DFS)
    static void dfs(int idx, int[] visit, Long[] num, char[] oper) {
        if (idx == 4) {
            cal(visit, num, oper); // 모든 우선순위 지정 완료 >> 계산
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (visit[i] == 0) {
                visit[i] = idx; // i번째 연산자에 우선순위 idx 부여
                dfs(idx + 1, visit, num, oper);
                visit[i] = 0; // 되돌리기 (백트래킹)
            }
        }
    }
}