[프로그래머스 *Java] - 수식 최대화

수식최대화

코딩테스트 연습 - 수식 최대화

---

👇 접근방식

처음에는 백준에서 풀었던 문제 중에, 연산자 끼워넣기랑 비슷하다고 생각을 했습니다.
그래서 그 기반으로 문제를 풀었습니다.
입력받은 식에서 피연산자와 연산자는 위치가 바뀌면 안됩니다.
그 상황에서 *, - , + 라는 세 연산자가 우선순위를 갖어 문제를 구현하는 방식입니다.
일단, 우선수위라는 건 세 연산자의 조합을 통해 총 6가지의 우선순위 조합을 갖는 다는 걸 알 수 있습니다.
이 부분은, String으로 미리 값을 넣던지, 방문처리 dfs로 조합을 만들어도 된다고 생각합니다.
중요한 건, 연산 작업을 하는 부분인데 (그림1) 을 보면 연산하는 작업을 볼 수 있습니다.

연산 작업 flow
0. 입력 받은 값을 연산자와 피연산자로 나뉘어 ArrayList에 담습니다.
1. 우선순위 조합을 한 세 가지의 연산자를 가지고 for 루프(loop_1)를 돕니다.
2. 루프(loop_1) 내에서 for 루프(loop_2)를 돌면서, 입력 받은 연산자 중에, 루프(loop_1) 순서대로 해당 연산자를 찾습니다.
3. 찾았다면, 연산자list 에서 해당 연산자를 지웁니다.
4. 동일하게 피연산지list 에서도 해당 피연산자를 지우는데(remove), 피연산자가 두 개를 가지고 연산을 하니, 뒷 피연산자만 제거(remove)를 하면서 뽑습니다.
5. 뒷 피연산자를 뽑은 걸로 앞 피연산자와 연산자를 이용하여, 계산을 해준 다음, 앞 피연산자의 idx에 연산한 값을 ArrayList.set 을 이용하여 update 시킵니다.
6. remove를 했기 때문에, idx 변화가 생겼으니 j-- 를 통해서 루프(loop_2) 내 인덱스를 맞춥니다.
7. 위 과정을 다 돈 뒤, Math.max 값을 비교합니다.
8. 최종적으로 가장 큰 값을 출력합니다.


[제한사항]
pression은 길이가 3 이상 100 이하인 문자열입니다.
expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
이로 인해서, 최대 피연산자는 50개, 연산자는 49개이며 피연산자는 최대값이 999일 것입니다.
그래서 최악의 상황은 999*50번을 하는 상황이라, 연산 값은 int범위를 넘는 우려가 생겨 long 자료형을 사용해야합니다.

(그림1). 연산자 우선순위 조합 : +, -, *

아래는 성공한 코드입니다.

 

첫 번째 풀이 방법

import java.util.*;

class Solution {
    
    private static boolean[] visited = new boolean[3]; // 방문처리 배열
    private static String[] priority = new String[3]; // 조합 담을 배열
    private static String[] arr = {"-", "*", "+"};
    private static ArrayList<String> operator = new ArrayList<>();
    private static ArrayList<Long> operand = new ArrayList<>();
    private static long max = Integer.MIN_VALUE;

    public static long calculate(String op, long op1, long op2) {
        long result = 0;

        switch (op) {
            case "+" :
                result = op1 + op2;
                break;

            case "-" :
                result = op1 - op2;
                break;

            case "*" :
                result = op1 * op2;
                break;
        }
        return result;
    }


    public static void dfs(int depth) {
        if (depth == 3) {
            ArrayList<String> tempOperator = new ArrayList<>();
            tempOperator.addAll(operator);
            ArrayList<Long> tempOperand = new ArrayList<>();
            tempOperand.addAll(operand);
            for (int i = 0; i < priority.length; i++) {
                for (int j = 0; j < tempOperator.size(); j++) {
                    if (priority[i].equals(tempOperator.get(j))) {
                        String op = tempOperator.remove(j);
                        long op1 = tempOperand.get(j);
                        long op2 = tempOperand.remove(j + 1);
                        long ans = calculate(op, op1, op2);
                        tempOperand.set(j, ans);
                        j--;
                    }
                }
            }
            max = Math.max(max, Math.abs(tempOperand.get(0)));
            return;
        }


        for (int i = 0; i < 3; i++) {
            if (!visited[i]) {
                visited[i] = true;
                priority[depth] = arr[i];
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static long solution(String expression) {
        long answer = 0;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            if (Character.isDigit(expression.charAt(i))) {
                sb.append(expression.charAt(i));
            }else {
                operand.add(Long.parseLong(sb.toString()));
                sb.setLength(0);
                operator.add(String.valueOf(expression.charAt(i)));
            }
        }
        operand.add(Long.parseLong(sb.toString()));
        dfs(0);
        return max;
    }
}

 

두 번째 풀이 방법

import java.util.*;

class Solution {
    public long calculatePriceMoney(long num1, long num2, char operator) {
        long result = 0;
        
        switch(operator) {
            case '+' :
                result = num1 + num2; 
                break;  
            case '-' :
                result = num1 - num2; 
                break;  
            case '*' :
                result = num1 * num2; 
                break;  
        }
        return result;
    }
    
    public long findMaxPriceMoney(String opType, ArrayList<Long> number, ArrayList<Character> operator) {
        long result = 0;
        
        for (int j = 0; j < opType.length(); j++) {
           for (int k = 0; k < operator.size(); k++) {
               if (opType.charAt(j) == operator.get(k)) {
                   long num1 = number.get(k);
                   long num2 = number.remove(k+1);
                   char op = operator.remove(k);
                   long calculatedNumber = calculatePriceMoney(num1, num2, op);                     
                   number.set(k, calculatedNumber);
                   k--;
               }
           }
        }
        return Math.abs(number.get(0));
    }
    
    public long solution(String expression) {
        ArrayList<Character> operator = new ArrayList<>();
        ArrayList<Long> number = new ArrayList<>();
        String[] operatorType = {
            "+-*",
            "+*-",
            "-+*",
            "-*+",
            "*+-",
            "*-*"
        };
        long answer = 0;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            if(Character.isDigit(expression.charAt(i))) {
                sb.append(expression.charAt(i));
            }else {
                number.add(Long.parseLong(sb.toString()));
                sb.setLength(0);
                operator.add(expression.charAt(i));
            }    
        }
        number.add(Long.parseLong(sb.toString()));
        for (int i = 0; i < operatorType.length; i++) {
            ArrayList<Long> tmpNumber = new ArrayList<>();
            tmpNumber.addAll(number);
            ArrayList<Character> tmpOperator = new ArrayList<>();
            tmpOperator.addAll(operator);
            long target = findMaxPriceMoney(operatorType[i], tmpNumber, tmpOperator);
            answer = Math.max(answer, target);
        }
            
        return answer;
    }
}