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

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

프로그래머스

코드:

 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    long answer = 0;
    List<Character> operands; // 사용된 연산자 종류 보관
    boolean[] isUsed;

    public long solution(String expression) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                set.add(c);
            }
        }
        operands = new ArrayList<>(set);
        isUsed = new boolean[operands.size()];
        recur(0, new ArrayList<>(), expression);
        return answer;
    }

    // 백트래킹
    public void recur(int cur, List<Integer> list, String expression) {
        if (cur == operands.size()) {
            List<Long> numList = new ArrayList<>(); //expression에서 피연산자 저장
            List<String> opList = new ArrayList<>();//expression에서 연산자 저장
            int left = 0;
            int right;
            for (right = 0; right < expression.length(); right++) {
                char c = expression.charAt(right);
                if (c < '0' || c > '9') {
                    numList.add(Long.valueOf(expression.substring(left, right)));
                    opList.add(String.valueOf(c));
                    left = right + 1;
                }
            }
            numList.add(Long.valueOf(expression.substring(left, right)));

            for (Integer idx : list) {
                String operand = String.valueOf(operands.get(idx));
                while(opList.contains(operand)) {
                    int i = 0;
                    for (String op : opList) { //연산자 인덱스 확인
                        if (!op.equals(operand)) ++i;
                        else break;
                    }
                    long result = 0;
                    switch (operand) {
                        case "+":
                            result = numList.get(i) + numList.get(i + 1);
                            break;
                        case "-":
                            result = numList.get(i) - numList.get(i + 1);
                            break;
                        case "*":
                            result = numList.get(i) * numList.get(i + 1);
                            break;
                    }
                    //배열 갱신
                    opList.remove(i);
                    numList.set(i, result);
                    numList.remove(i + 1);
                }
            }
            answer = Math.max(answer, Math.abs(numList.get(0)));
            return;
        }

        for (int i = 0; i < operands.size(); i++) {
            if(isUsed[i]) continue;
            List<Integer> tmp = new ArrayList<>(list);
            tmp.add(i);
            isUsed[i] = true;
            recur(cur + 1, tmp, expression);
            isUsed[i] = false;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        String expression = "100-200*300-500+20";
        long answer = sol.solution(expression);
        System.out.println(answer);
    }
}

 

처음에는 피연산자를 계산할 때 마다 문자열 형태로 expression에 저장했는데 이렇게 하면 음수에 조건이 많아져서 오류를 해결하지 못했다. 이런 수를 다룰 때는 String으로 풀지말고 수 타입을 이용하자