[프로그래머스] 수식 최대화(java)

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

이 문제는 각각의 연산자에 우선순위를 부여하여 각각의 우선순위대로 계산했을 때 절댓값이 가장 큰 경우를 찾는 것이다.

 

핵심

연산자가 +, -, * 3가지이기 때문에 연산자의 우선순위의 경우의 수는 6가지이다.

따라서 다소 빡구현을 통해 풀 수 도 있지만, 조합을 이용하면 더 간결하게 작성할 수 있다.

 

정답 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    static long answer = 0;
    static String expression;
    static List<Long> numbers;
    static List<Character> operation;

    public long solution(String expression) {
        this.expression = expression;
        divisionExpression();
        permutation(0, 3, new char[]{'+', '-', '*'}, new boolean[3], "");
        return answer;
    }

    private void divisionExpression() {
        StringBuilder number = new StringBuilder();
        numbers = new ArrayList<>();
        operation = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
                numbers.add(Long.parseLong(number.toString()));
                number = new StringBuilder();
                operation.add(expression.charAt(i));
                continue;
            }
            number.append(expression.charAt(i));
        }
        numbers.add(Long.parseLong(number.toString()));
    }

    private void permutation(int index, int target, char[] operation, boolean[] check, String result) {
        if (index == target) {
            calc(result);
            return;
        }
        for (int i = 0; i < 3; i++) {
            if (!check[i]) {
                check[i] = true;
                permutation(index + 1, target, operation, check, result + operation[i]);
                check[i] = false;
            }
        }
    }

    private void calc(String operator) {
        List<Long> nowNumbers = new ArrayList<>(numbers);
        List<Character> nowOperation = new ArrayList<>(operation);
        for (int i = 0; i < operator.length(); i++) {
            char now = operator.charAt(i);
            int index;
            while (nowOperation.size() != 0) {
                index = nowOperation.indexOf(now);
                if (index == -1) {
                    break;
                }
                switch (now) {
                    case '+':
                        nowNumbers.add(index, nowNumbers.get(index) + nowNumbers.get(index + 1));
                        break;
                    case '-':
                        nowNumbers.add(index, nowNumbers.get(index) - nowNumbers.get(index + 1));
                        break;
                    case '*':
                        nowNumbers.add(index, nowNumbers.get(index) * nowNumbers.get(index + 1));
                        break;
                }
                nowNumbers.remove(index + 1);
                nowNumbers.remove(index + 1);
                nowOperation.remove(index);
            }
        }
        answer = Math.max(answer, Math.abs(nowNumbers.get(0)));
    }
}

해설

우선 expression을 각각의 수와 연산자로 분리하는 작업이 필요하다.

메서드 divisionExpression을 보면 연산자가 나오기 전까지 StringBuilder를 통해 수를 연결하고 이후 연산자가 나오면 

그 수를 numbers에 넣고, 연산자 자체는 operation에 넣어준다. 마지막의 경우 연산자가 나오지 않기 때문에 반복문 이후에 

남은 수를 numbers에 넣어줘야 한다.

 

메서드 permutation은 +, -, *의 조합을 통해 +-*, +*-,... 와같은 6개의 경우의 수가 나오게 된다.

이후 이 조합을 가지고 calc메서드에서 값을 구하게 된다.

연산자를 우선순위대로 계산해 준다. 이때 indexOf를 사용하여 해당 연산자가 없다면 다음 연산자를 수행하게 된다.

스위치문을 보면 numbers.add()가 있는데 이는 만약 [500, 20]에 + 연산자라면 [520, 500, 20]이 된다.

따라서 remove를 통해 500과 20 둘 다 지워주고, 사용한 연산자 또한 제거해 준다.

 

배운 점

수를 계산하는 과정을 어떤 식으로 할지 많은 고민을 하였다. 그 결과 리스트 내에서 계산하고 제거를 반복하여 해결하였다.

처음에는 calc 메서드 안에서 divisionExpression을 반복하였는데, 이 결과 성능이 떨어질 것이라 생각하였다.

따라서 divistionExpression을 처음에 시행하고 calc에는 copy를 하여 사용하도록 수정하였다.

어렵기보다는 구현할게 생각보다 좀 많은 느낌이다. 재미있는 문제라고 생각된다.