프로그래머스 - 수식 최대화

오늘 풀어본 문제는 ⭐수식 최대화 이다.

1. 문제 요약

• 3가지 연산 기호 +, -, *의 우선순위를 다르게 설정하여 계산
• 주어진 수식에서 만들 수 있는 결과값의 절댓값 중 최댓값을 구하는 문제
• 계산 과정에서 음수 결과가 발생할 수 있으므로 - 연산자와 음수 값의 구분이 필요
• 연산자 우선순위는 총 3! = 6가지 조합이 존재하므로 모든 경우를 확인해야 함.

2. 입출력

입력

• expression
  • 숫자와 연산자(+, -, *)로 이루어진 문자열
  • 길이: 3 이상 100 이하
• 계산 중 값이 커질 수 있으므로 long 타입 사용

출력

• 주어진 식에서 연산자 우선순위를 적절히 설정했을 때 얻을 수 있는 결과값의 절댓값 중 최댓값 반환

3. 알고리즘

1. 수식 파싱

• StringTokenizer를 이용하여 수식을 숫자 리스트(nums)와 연산자 리스트(ops)로 분리한다.

• 예시
  100-200*300-500+20

  nums = [100, 200, 300, 500, 20]
  ops = ['-', '*', '-', '+']

2. 연산자 우선순위 경우의 수 생성

• 가능한 연산자는 +, -, * 총 3개
• 모든 우선순위 경우는 3! = 6가지
• permute()를 사용하여 연산자 우선순위 순열 생성

3. 우선순위에 따른 계산

• 각 우선순위마다 evaluate() 실행
• 연산자 우선순위 순서대로 식을 계산하면서 리스트를 줄여나감

[예시]

초기 상태
nums = [100, 200, 300, 500, 20]
ops = ['-', '*', '-', '+']

---

우선순위가 * 먼저일 경우

• ops[1] = *;
• nums[1]과 nums[2]가 피연산자!

즉 200 * 300 = 60000 의 새로운 결과 도출됨

리스트 갱신

1) 60000의 결과값을 현재 nums[i] 에 넣음 (i=1)
- nums = [100, 60000, 300, 500, 20]

nums.set(i, 60000);

2) 쓰인 피연산자 300을 nums에서 삭제해줌

nums.remove(i + 1);

3) 쓰인 연산자 *을 ops에서 삭제해줌
- ops = ['-', '-', '+']

ops.remove(i);

---

이 과정을 우선순위 순서대로 반복

4. 최대 절댓값 갱신

• 모든 계산이 끝나면 결과는 nums[0]
• 결과의 절댓값을 계산하여 최대값 갱신

best = max(best, abs(result))

5. 최종 결과 반환

• 모든 우선순위(6가지)를 검사한 후
• 가장 큰 절댓값 반환

4. 코드

import java.util.*;

class Solution {
    private static final char[] OPS = {'+', '-', '*'};
    private static boolean[] used;
    private static long best;

    public long solution(String expression) {
        List<Long> nums = new ArrayList<>();
        List<Character> ops = new ArrayList<>();
        used = new boolean[3];
        
        parse(expression, nums, ops);
        permute(0, new char[3], nums, ops);

        return best;
    }

    private static void parse(String expr, List<Long> nums, List<Character> ops) {
        StringTokenizer st = new StringTokenizer(expr, "+-*", true);

        while (st.hasMoreTokens()) {
            String token = st.nextToken();

            if (token.equals("+") || token.equals("-") || token.equals("*")) {
                ops.add(token.charAt(0));
            } else {
                nums.add(Long.parseLong(token));
            }
        }
    }

    private static void permute(int depth, char[] order, List<Long> baseNums, List<Character> baseOps) {
        if (depth == 3) {
            long val = evaluate(order, baseNums, baseOps);
            best = Math.max(best, Math.abs(val));
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (used[i]) continue;
            used[i] = true;
            order[depth] = OPS[i];
            permute(depth + 1, order, baseNums, baseOps);
            used[i] = false;
        }
    }

    private static long evaluate(char[] order, List<Long> baseNums, List<Character> baseOps) {
        // ⭐복사본에서 작업
        List<Long> nums = new ArrayList<>(baseNums);
        List<Character> ops = new ArrayList<>(baseOps);

        for (char target : order) {
            for (int i = 0; i < ops.size(); ) {
                if (ops.get(i) == target) {
                    long a = nums.get(i);
                    long b = nums.get(i + 1);
                    long r = calc(a, b, target);

                    nums.set(i, r);
                    nums.remove(i + 1);
                    ops.remove(i);
                } else {
                    i++;
                }
            }
        }
        return nums.get(0);
    }

    private static long calc(long a, long b, char op) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        return a * b;
    }
}