프로그래머스(Java) - 수식 최대화

문제 링크

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

문제 풀이

expression는 하나의 긴 문자열처럼 되어있으므로 이것을 숫자와 연산자로 나눠서 parsing했다.
tot 에는 전체
oper에는 연산자
number에는 숫자만

String [] temp = expression.split("\\+|-|\\*");
        List<String>tot = new ArrayList();
        List<String>oper = new ArrayList();
        List<Long> number = new ArrayList();
        for(int i=0; i<temp.length; i++){
            number.add(Long.parseLong(temp[i]));
        }
        String savenum = "";
        for(int i=0; i<expression.length(); i++){
            String now = expression.substring(i,i+1);
            if(!"".equals(savenum) && (now.equals("+") || now.equals("-") || now.equals("*")) ){
                tot.add(savenum);
                tot.add(now);
                savenum="";
            }else{
                savenum+=now;
            }
            if(i==expression.length()-1){
                tot.add(savenum);
            }
        }
        if(expression.contains("*")){
            oper.add("*");
        }
        if(expression.contains("+")){
            oper.add("+");
        }
        if(expression.contains("-")){
            oper.add("-");
        }

oper는 +,-,* 가 중복없이 저장되므로 oper.size()에 따라 반복되는 logic을 다르게 처리했다.
하지만 공통적으로 Deque를 사용했는데 Stack, Queue 2개 중에서 고민을 했는데 각각 내가 생각한 로직을 수행하기에는 부족한 점이 한가지씩 있었다.

특정 연산기호가 등장했을때 그 연산기호 다음값과, 연산기호 이전값을 연산하고 다시 자료구조에 넣는 로직을 생각했는데 queue로 하기에는 뒤에서부터 빼낼수가 없고, stack으로 하기에는 연산기호 2~3개 일때 연산을 처리할수가 없었다.
그래서 앞,뒤에서 빼네는것이 자유로운 deque를 사용하기로 했다.

oper.size()가 1인 경우
deque에 tot에 있는값들을 add하다가 특정 연산자가 나오면 dq의 뒤에서 연산자, 마지막에 저장된 숫자를 뽑아서 tot의 값과 연산처리를 하고 다시 dq에 저장한다.
연산자의 종류가 하나이므로 무조건 연산이 진행되고, 마지막 연산까지 하게되면 dq의 size는 1 되어야만 한다. 그값을 절대값을 적용하여 출력한다.

oper.size()==2,3인경우
기본적으로 size()가 1인경우와 로직은 똑같지만 연산자를 2,3개 처리해야하므로
우선 순위에 따른 나올수 있는 2가지 , 6가지 경우에 대해서 for문을 돌아야한다.
우선순위인 연산자가 나왔을경우에만 연산을 처리하고, dq에서 우선순위인 연산자의 logic이 끝나면 다음 연산자를 가지고 dq2에서 연산을 진행한다.
3개인 경우도 동일하다.

코드

import java.util.*;

class Solution {
    public long solution(String expression) {
        long answer = 0;
        
        String [] temp = expression.split("\\+|-|\\*");
        List<String>tot = new ArrayList();
        List<String>oper = new ArrayList();
        List<Long> number = new ArrayList();
        for(int i=0; i<temp.length; i++){
            number.add(Long.parseLong(temp[i]));
        }
        String savenum = "";
        
        for(int i=0; i<expression.length(); i++){
            String now = expression.substring(i,i+1);
            if(!"".equals(savenum) && (now.equals("+") || now.equals("-") || now.equals("*")) ){
                tot.add(savenum);
                tot.add(now);
                savenum="";
            }else{
                savenum+=now;
            }
            
            if(i==expression.length()-1){
                tot.add(savenum);
            }
        }
        
        if(expression.contains("*")){
            oper.add("*");
        }
        if(expression.contains("+")){
            oper.add("+");
        }
        if(expression.contains("-")){
            oper.add("-");
        }

        if(oper.size()==1){
            Deque<String> dq = new ArrayDeque<String>();
            dq.add(tot.get(0));
            for(int i=1; i<tot.size(); i++){
                if(dq.peekLast().equals("*") || dq.peekLast().equals("+")  || dq.peekLast().equals("-") ){
                     String op = dq.pollLast();
                     dq.add(String.valueOf(operatorSetting(op,Long.parseLong(dq.pollLast()),Long.parseLong(tot.get(i)))));
                }else{
                     dq.add(tot.get(i));
                }
                //System.out.println(dq.toString());
            }
            answer = Math.abs(Long.parseLong(dq.poll()));
        }else if(oper.size()==2){
            String [] opers = {oper.get(0), oper.get(1)};
            for(int i=0; i<2; i++){
                Deque<String> dq = new ArrayDeque<String>();
                Deque<String> dq2 = new ArrayDeque<String>();
                dq.add(tot.get(0));
                for(int j=1; j<tot.size(); j++){
                    if(dq.peekLast().equals(opers[1-i])){
                         String op = dq.pollLast();
                         dq.add(String.valueOf(operatorSetting(op,Long.parseLong(dq.pollLast()),Long.parseLong(tot.get(j)))));
                    }else{
                         dq.add(tot.get(j));
                    }
                    //System.out.println(dq.toString());
                }
                dq2.add(dq.poll());
                while(!dq.isEmpty()){
                    if(dq2.peekLast().equals(opers[i])){
                         String op = dq2.pollLast();
                         dq2.add(String.valueOf(operatorSetting(op,Long.parseLong(dq2.pollLast()),Long.parseLong(dq.poll()))));
                    }else{
                         dq2.add(dq.poll());
                    }
                    //System.out.println(dq2.toString());
                }
                answer = Math.max(Math.abs(answer), Math.abs(Long.parseLong(dq2.poll())));
                   
            }//i for문
        }else{//size() ==3 
             String [] opers ={"+-*","+*-","-+*","-*+","*+-","*-+"};
             for(int i=0; i<6; i++){
                 String [] operationss = opers[i].split("");
                 Deque<String> dq = new ArrayDeque<String>();
                 Deque<String> dq2 = new ArrayDeque<String>();
                 Deque<String> dq3 = new ArrayDeque<String>();
                 dq.add(tot.get(0));
                 for(int j=1; j<tot.size(); j++){
                    if(dq.peekLast().equals(operationss[0])){
                         String op = dq.pollLast();
                         dq.add(String.valueOf(operatorSetting(op,Long.parseLong(dq.pollLast()),Long.parseLong(tot.get(j)))));
                    }else{
                         dq.add(tot.get(j));
                    }
                    //System.out.println(dq.toString());
                 }
                 dq2.add(dq.poll());
                 
                 while(!dq.isEmpty()){
                    if(dq2.peekLast().equals(operationss[1])){
                         String op = dq2.pollLast();
                         dq2.add(String.valueOf(operatorSetting(op,Long.parseLong(dq2.pollLast()),Long.parseLong(dq.poll()))));
                    }else{
                         dq2.add(dq.poll());
                    }
                    //System.out.println(dq2.toString());
                 }
                 dq3.add(dq2.poll());
                 while(!dq2.isEmpty()){
                    if(dq3.peekLast().equals(operationss[2])){
                         String op = dq3.pollLast();
                         dq3.add(String.valueOf(operatorSetting(op,Long.parseLong(dq3.pollLast()),Long.parseLong(dq2.poll()))));
                    }else{
                         dq3.add(dq2.poll());
                    }
                    //System.out.println(dq3.toString());
                 }
                 answer = Math.max(Math.abs(answer), Math.abs(Long.parseLong(dq3.poll())));
                 // System.out.println("return : "+answer);
                 // System.out.println("===============");
             }        
        }
        return answer;
    }
       
    public static long operatorSetting(String oper, long a, long b){
        
        if(oper.equals("*")){
            return a*b;
        }else if(oper.equals("+")){
            return a+b;
        }else{
            return a-b;
        }
    } 
}