문제

문제링크

접근

• 스택을 활용한 연산을 할 때 우선순위를 사용하여 더 꺼낼지 말지 판단한다.
• 그래서 이 문제도 그 우선순위에 대하여 완전탐색하면 최대값을 구할 수 있다.
• 정규식으로 연산자와 피연산자를 각각 처리하여 쉽게 파싱하였다.
• 내부 값이 딱히 필요 없기 때문에 속도 향상을 위하여 Dequq를 사용한다.

소스코드

import java.util.*;

class Solution {
    int[][] grades = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};    // *+-
    Deque<Long> ns = new ArrayDeque<>();
    Deque<Character> os = new ArrayDeque<>();
    int T = -1;
    long answer = -1;
    char[] ops;
    int[] nums;
    public long solution(String expression) {
        String numStr = expression.replaceAll("[*+-]", " ");
        String[] numStrs = numStr.split(" ");
        ops = expression.replaceAll("[0-9]", "").toCharArray();

        nums = new int[numStrs.length];
        for (int i = 0; i < numStrs.length; i++)
            nums[i] = Integer.parseInt(numStrs[i]);
        
        for (int i = 0; i < 6; i++) {
            T = i;
            answer = Math.max(getResult(), answer);
        }
        
        return answer;
    }
    
    private long getResult() {
        ns.push(Long.valueOf(nums[0]));
        for (int i = 1; i < nums.length; i++) {            
            while (!os.isEmpty() && grade(os.peek()) >= grade(ops[i-1])) {
                Long a = ns.pop();
                Long b = ns.pop();
                ns.push(calc(b, a, os.pop()));
            }
            
            ns.push(Long.valueOf(nums[i]));
            os.push(ops[i-1]);
        }
        
        while (!ns.isEmpty()) {
            Long a = ns.pop();
            Long b = ns.pop();
            ns.push(calc(b, a, os.pop()));
            if (ns.size() == 1) break;
        }
        
        return Math.abs(ns.pop());
    }
    
    private Long calc(Long a, Long b, char c) {
        if (c == '*') return Long.valueOf(a * b);
        if (c == '+') return Long.valueOf(a + b);
        return Long.valueOf(a - b);
    }
    
    private int grade(char c) {
        int idx = c == '*' ? 0 : c == '+' ? 1 : 2;
        return grades[T][idx];
    }
}