[프로그래머스] 수식 최대화 / 2020 카카오 인턴십 - JAVA

🔗 문제 링크

[프로그래머스] 수식 최대화 / 2020 카카오 인턴십

📝 풀이 과정

연산자의 우선순위를 permutation을 사용해 모든 경우를 구한 뒤, 우선순위가 높은 연산자를 먼저 계산해 누적하는 방식으로 계산하였다.

계산기를 구현할 때 사용하는 방식으로 연산자를 Stack에 쌓아 현재 쌓인 연산자의 우선순위 이하의 연산자가 들어온 경우 계산해 누적하였다.

 

 

💡 StringTokenizer는 생성할 때, new String(String str, String delim, boolean returnDelims)로도 생성할 수 있다.

str에서 delims에 포함된 character를 기준으로 분할한다 (String 기준❌)
returnDelims가 true일 경우 delims도 token으로 취급해 반환해 준다!

 

💻 코드

import java.util.*;

class Solution {
    long ans = Integer.MIN_VALUE;
    int[] perm = new int[3];
    boolean[] visit = new boolean[3];
    Map<Character, Integer> priority = new HashMap<>();
    List<Long> numList = new ArrayList<>();
    List<Character> opList = new ArrayList<>();

    public long solution(String expression) {
        StringTokenizer st = new StringTokenizer(expression, "+-*", true);

        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if ("+-*".contains(token)) opList.add(token.charAt(0));
            else numList.add(Long.parseLong(token));
        }
        permutation(0);
        System.out.println(ans);

        return ans;
    }

    public void solve() {
        Deque<Long> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();

        numStack.push(numList.get(0));
        for (int i = 0, size = opList.size(); i < size; i++) {
            char op = opList.get(i);
            while (!opStack.isEmpty() && priority.get(opStack.peek()) >= priority.get(op)) {
                numStack.push(calc(numStack.pop(), numStack.pop(), opStack.pop()));
            }

            numStack.push(numList.get(i + 1));
            opStack.push(op);
        }

        while (numStack.size() > 1) {
            numStack.push(calc(numStack.pop(), numStack.pop(), opStack.pop()));
        }

        ans = Math.max(ans, Math.abs(numStack.pop()));
    }

    public void permutation(int idx) {
        if (idx == 3) {
            priority.put('+', perm[0]);
            priority.put('-', perm[1]);
            priority.put('*', perm[2]);

            solve();
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            perm[idx] = i;
            permutation(idx + 1);
            visit[i] = false;
        }
    }

    public long calc(long n1, long n2, char op) {
        if (op == '+')
            return n1 + n2;
        else if (op == '-')
            return n2 - n1;
        else return n1 * n2;
    }
}