알고리즘 풀이/프로그래머스

[level2] 프로그래머스 - 수식 최대화(JAVA)

데롱디롱 2021. 9. 10. 01:45
728x90

 

 

[ 문제 풀이 ]

1. 연산자 우선순위로 가능한 우선순위를 배열로 만든다.

String op[][] = { { "+", "-", "*" }, { "+", "*", "-" }, { "-", "*", "+" }, { "-", "+", "*" }, { "*", "-", "+" }, { "*", "+", "-" } };

 

 

2. 문자열에서 숫자와 연산자를 분리해, ArrayList에 추가한다.
       - 연산자를 만나면, 앞은 숫자이므로 먼저 추가 -> 연산자 추가
       - 계속 연산자 앞 숫자만 추가했으므로, 마지막 숫자도 빼먹지말고 추가해준다.

ArrayList<String> list = new ArrayList<String>();
int start = 0;
for (int i = 0; i < expression.length(); i++) {
       if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {            
             list.add(expression.substring(start, i)); // 연산자 앞 숫자 추가
             list.add(expression.charAt(i) + ""); // 연산자 추가
             start = i + 1;
       }
}
list.add(expression.substring(start)); // 마지막 숫자 추가

 

 

3. 연산자 우선순위 6개의 경우에 대해 계산을 한다.

       - 우선순위 순서대로 수식을 계산한다.     => op[i][0]   ->   op[i][1]   ->   op[i][2]

 

 

4. list에서 op[i][k]에 해당하는 수식을 만나면,
       - 자신은 수식 기호( +, -, * )이므로 자신의 앞에 값 ( +, -, * ) 자신의 다음 값 계산을 해준다.

       - 계산한 값으로 앞의 숫자를 바꾼다.

       - 계산을 마친 수식과 자신 다음에 위치한 숫자를 제거해준다.

 

 

5. 수식 계산이 끝나면, 계산을 마친 값은 sub_list의 0번 인덱스에 저장이 되어있다.
    이 숫자의 절댓값과 max의 최댓값을 비교한다.

 

 

 

 

[ 전체 코드 ]

import java.util.ArrayList;

class Solution {
    public static long solution(String expression) {
        long answer = Long.MIN_VALUE;
        String op[][] = { { "+", "-", "*" }, { "+", "*", "-" }, { "-", "*", "+" }, 
                         { "-", "+", "*" }, { "*", "-", "+" }, { "*", "+", "-" } };

        ArrayList<String> list = new ArrayList<String>();
        int start = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
                list.add(expression.substring(start, i)); // 연산자 앞 숫자 추가
                list.add(expression.charAt(i) + ""); // 연산자 추가
                start = i + 1;
            }
        }
        list.add(expression.substring(start)); // 마지막 숫자 추가

        for (int i = 0; i < op.length; i++) {
            ArrayList<String> sub_list = new ArrayList<String>(list);
            for (int k = 0; k < 3; k++) {
                for (int j = 0; j < sub_list.size(); j++) {
                    if (op[i][k].equals(sub_list.get(j))) {
                        sub_list.set(j - 1, calc(sub_list.get(j - 1), sub_list.get(j), sub_list.get(j + 1)));
                        sub_list.remove(j);
                        sub_list.remove(j);
                        j--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(Long.parseLong(sub_list.get(0))));
        }

        return answer;
    }

    private static String calc(String num1, String op, String num2) {
        long n1 = Long.parseLong(num1);
        long n2 = Long.parseLong(num2);

        if (op.equals("+"))
            return n1 + n2 + "";
        else if (op.equals("-"))
            return n1 - n2 + "";

        return n1 * n2 + "";
    }
}