[JAVA] 2020 카카오 인턴십 【수식 최대화】

---

문자열을 어떻게 처리할까 굉장히 많이 고민했던 문제였다.

 

정규식을 사용하는게 코드가 더 간결해질 것 같아서 정규식을 사용했다.

 

그리고, 연산자는 + - * 3개만 주어지기 때문에, 연산자 우선순위를 직접 명시해서 선언해주었다.

 

"*+-","+*-","*-+","+-*","-*+","-+*"

 

위와 같은 6가지 경우가 있을 수 있다.

 

먼저 정규식 "\\d+|\\S" 를 사용하면, 숫자와 연산자로 나눌 수 있다.

 

그리고, 정규식을 바탕으로 분리한 원소들을, 순회하면서 숫자라면 스택에 집어넣고, 연산자이면서 우선순위에 해당하는 연산자라면 스택에 있던 숫자를 빼서 연산처리 한 뒤, 넣어놓는 방식으로 표현식을 변환시켰다.

 

우선순위가 "*+-" 라고 가정했을때 "100-200*300-500+20" 이 식은

 

"100-60000-500+20" 으로 변환되고 "100-60000-520" 이 변환되고 "-60420" 이 되는 것이다.

 

다만, 여기서 주의할 점이 있는데

 

만약 "100-200*300-500+20" 이 식에서 "-" 연산을 먼저 수행하면

 

"-100*-200+20" 이 되고 이 식을 다시  "\\d+|\\S"  이 정규식을 사용하게 되면

[ - , 100 , * , - , 200 , + , 20 ] 와 같이 분리가 된다는 점이다.

 

따라서, - 연산이 수행되고 나서는 피연산자가 음수가 되는 경우가 생기므로, 정규식을 "-?\\d+|\\S" 를 사용해야 에러를 방지할 수 있었다.

 

 

정규식을 간략하게 설명하면, 

 

-? 는 - 기호가 있을 수도 없을 수도 있음을 나타낸다. (있는 경우 최대 1개)

\\d+ 는 연속된 숫자를 나타내고

| 는 또는 을 나타내고

\\S 는 공백이 아닌 문자를 나타낸다.

 

 

---

 

import java.util.*;
import java.util.regex.*;

class Solution {
    Deque<String> q;
    public long solution(String expression) {

        long answer = 0;
        q = new ArrayDeque<>();
        String[] pri = {"*+-","+*-","*-+","+-*","-*+","-+*"};

        for(int i=0;i<pri.length;i++){

            boolean flag = true;
            String[] ops = pri[i].split("");
            String ex = expression;

            for(int j=0;j<ops.length;j++){

                String op = ops[j];
                Pattern p;
                Matcher m;

                if(flag){
                    p = Pattern.compile("\\d+|\\S");
                    m = p.matcher(ex);
                }else{
                    p = Pattern.compile("-?\\d+|\\S");
                    m = p.matcher(ex);
                }

                if(op.equals("-")){
                    flag = false;
                }

                while(m.find()){
                    String s = m.group();
                    if(s.equals(op)){
                        m.find();
                        q.offer(String.valueOf(getValue(q.pollLast(),m.group(),op)));
                    }else{
                        q.offer(s);
                    }
                }
                ex = toEx();
            }
            answer = Math.max(answer,Math.abs(Long.parseLong(ex)));
        }
        return answer;
    }

    long getValue(String num1,String num2,String op){
        long n1 = Long.parseLong(num1);
        long n2 = Long.parseLong(num2);
        if(op.equals("*")){
            return n1*n2;
        }else if(op.equals("+")){
            return n1+n2;
        }else{
            return n1-n2;
        }
    }

    String toEx(){
        StringBuilder sb = new StringBuilder();
        for(String str : q){
            sb.append(str);
        }
        q.clear();
        return sb.toString();
    }

}