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

문제 - (https://programmers.co.kr/learn/courses/30/lessons/67257)

연산자를 사용하는 문제였다

100-200*300-500+20이라는 문자열이 주어진다면, 원래대로라면 [*] -> [+,-] 순서로 연산을 진행해야 하지만

문제에서는 연산자 우선순위 순서를 다르게 했을 때, 결과값의 절댓값이 최대가 될 때의 값을 원했다.

참고로, 위 문자열은 *, +, - 순서로 우선순위를 줬을 때, -60420이라는 값이 나오게 된다.

절댓값이 60420이므로 가장 큰 수가 되서 답이 된다.

 

처음에는 연산자 우선순위를 두고 어떻게 계산할까 고민하다가

보통 이런 문제 스택을 사용했던 것 같아서 스택으로 풀어보려고 했다.

하지만 생각보다 너무 어려웠다.... 그래서 다르게 생각해본 방법은 이렇다.

 

1. 주어진 식을 연산자와 숫자로 배열 cals를 만든다.
   ex) 100, -, 200, *, 300, -, 500, +, 20 < 이런 식으로
2. 재귀로 순열을 구해서 연산자 순서를 정한다.
3. cals 배열을 clone 한 temp배열을 만든다.
   (temp배열에는 우선순위대로 계산하여 계산된 결과로 값을 바꾸고 계산된 것들은 NULL로 바꿀 예정이다)
4. cals 배열을 순회하면서 계산할 연산자들을 찾는다.
5. 수행할 연산자를 발견하면, 그 연산자의 왼쪽과 오른쪽에 존재하는 숫자를 찾는다.
   (이때, 이미 이전에 계산되어 버려서 NULL이 있는 경우는 계속해서 왼쪽, 오른쪽으로 진행하면서 값을 찾는다)
6. 발견한 숫자를 현재 연산자로 계산한다. 그리고 그 결과를 temp 배열에 저장한다. 숫자 부분은 NULL로 바꾼다.
   ex) 100, +, 200이었으면 NULL, 300, NULL
7. 3~6을 연산자 우선순위 순서대로 끝까지 반복한다
8. temp배열에 NULL이 아닌 값이 존재하면 그것이 답이 된다.

대략 적어봤는데...

코드에도 주석을 해놨으니 코드를 보는 게 더 편할 수 있겠다.

분명 이 코드보다 더 좋은 코드가 있을 것이다.

나중에 시간을 내서 다른 사람은 어떻게 풀었는지 확인해봐야겠다

 

---

😅실수

• selectedOp [i] 배열은 i번째에 어떤 연산자를 먼저 계산할 것인지 정하기 위한 배열이다. 재귀의 k값이 인덱스가 되어야 하지, i 값이 인덱스가 되면 안 된다.

 

---

코드

import java.util.StringTokenizer;

public class OperationMax {
    static final char[] ops = {'+', '-', '*'};
    static boolean[] visitedOp = new boolean[3];
    static char[] selectedOp = new char[3];
    static String[] cals;
    static int size;
    static long answer;

    static void maximize(int k) {
        if (k == 3) {
            // 선택된 연사자 순서로 계산시작
            String[] temp = cals.clone();
            for (int i = 0; i < 3; i++) {
                char curOp = selectedOp[i];

                // cals를 순회하면서 curOp와 일치하는 연산자의 계산을 수행한다
                for (int j = 0; j < size; j++) {
                    if (cals[j].equals(curOp + "")) {
                        long left = findLeft(j - 1, temp); // j에서부터 배열의 왼쪽으로 계속 이동하여 숫자를 찾고, 그 자리를 Null로 바꾼다.
                        long right = findRight(j + 1, temp); // j에서부터 배열의 오른쪽으로 계속 이동하여 숫자를 찾고, 그 자리를 Null로 바꾼다.
                        long res = calc(left, right, curOp); // 찾은 숫자들을 계산한다
                        temp[j] = res + ""; // 해당 위치를 계산된 결과로 바꾼다
                    }
                }
            }
            for (String t : temp) {
                // Null이 아닌 단 하나의 원소가 현재 연산자 순서로 계산했을 때 도출할 수 있는 결과임.
                if (t != null) {
                    answer = Math.max(answer, Math.abs(Long.parseLong(t)));
                    return;
                }
            }
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (visitedOp[i]) continue;
            visitedOp[i] = true;
            selectedOp[k/* <- 이거 i가 아니라 k임!!! 실수하지말자!!!!!! */] = ops[i];
            maximize(k + 1);
            visitedOp[i] = false;
        }
    }

    static long findLeft(int idx, String[] cal) {
        if (cal[idx] == null) {
            return findLeft(idx - 1, cal);
        }
        long ret = Long.parseLong(cal[idx]);
        cal[idx] = null;
        return ret;
    }

    static long findRight(int idx, String[] cal) {
        if (cal[idx] == null) {
            return findRight(idx + 1, cal);
        }
        long ret = Long.parseLong(cal[idx]);
        cal[idx] = null;
        return ret;
    }

    static long calc(long a, long b, char op) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
        }
        return 0;
    }

    static long solution(String expression) {
        // 연산자를 제거하여
        StringTokenizer stNum = new StringTokenizer(expression, "+-*");
        StringTokenizer stOp = new StringTokenizer(expression, "0123456789");
        size = stNum.countTokens() + stOp.countTokens();

        cals = new String[size];

        for (int i = 0; i < size; i++) {
            if (i % 2 == 0) {
                cals[i] = stNum.nextToken();
            } else {
                cals[i] = stOp.nextToken();
            }
        }

        maximize(0);

        return answer;
    }

    public static void main(String[] args) {
        String expression = "100-200*300-500+20";
        String expression2 = "50*6-3*2";

        System.out.println(solution(expression2));
    }
}