수식 최대화

문제

프로그래머스

수식이 주어지면, 연산자의 우선순위를 임의를 바꿔 최댓값을 구하는 문제이다.

예를 들어 "100-200*300-500+20" 식이 주어지면, * > + > - 순서로 연산자의 우선순위를 정해주면

100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420

음수의 결과값은 절댓값을 취해준다.

 

연산자는 총 "*", "+", "-" 3가지가 나온다.

---

먼저 연산자 순위의 모든 경우의 수를 만들어준다.

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

 

그 다음 주어진 expression을 연산자와 숫자를 분리해 List에 저장해준다.

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

 

그 다음 우선순위에 따라 list를 순회하면서 연산자를 만나면 계산해준다.

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

.set(i, j) 는 i번째 인덱스를 j로 대체하는 함수이다.

해당 연산자가 나오면 연산자 기준 양 옆에 있는 숫자를 계산 해주고, subList의 이전 element를 삭제한다.

계산된 element는 j-1에 위치해 있기 때문이다.

모든 연산자가 순회하고 계산이  다된 숫자는 subList의 0번째 인덱스에 위치한다.

 

cal() 의 코드이다.

static String cal(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 +"";
    }

---

전체 코드이다.

import java.util.*;
class Solution {
    public long solution(String expression) {
        long answer = -1;
        String op[][] ={ { "+", "-", "*" }, { "+", "*", "-" }, { "-", "*", "+" },  { "-", "+", "*" }, { "*", "-", "+" }, { "*", "+", "-" } };
        
        List<String>list = new ArrayList<>();
        int start = 0;
        for(int i = 0; i< expression.length();i++){
            char ch = expression.charAt(i);
            if(ch == '-' || ch == '+' || ch=='*'){
                list.add(expression.substring(start, i));//숫자 추가
                list.add(ch+"");//연산자 추가
                start = i+1;
            }
        }
        list.add(expression.substring(start)); //마지막 숫자 추가
        
        for(int i = 0;i<op.length;i++){
            List<String>subList = new ArrayList<String>(list);
            for(int k = 0;k<3;k++){
                for(int j = 0;j<subList.size();j++){
                    if(op[i][k].equals(subList.get(j))){
                        subList.set(j-1, cal(subList.get(j-1), subList.get(j), subList.get(j+1)));
                        subList.remove(j);
                        subList.remove(j);
                        j--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(Long.parseLong(subList.get(0))));
        }
        return answer;
    }
    static String cal(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 +"";
    }
}