[구현]프로그래머스 수식최대화 (실패 분석 - 시간 부족)

접근

수식최대화

이 문제는 단순 구현 문제입니다.

문제를 풀면서 든 생각은 종이에 어떻게 접근할 것인지
정리하는 습관이 있어야겠다는 것이었습니다.

일단 이 문제는 연산자의 우선순위를 만들어서
수식이 최대가 나오도록 만드는 문제입니다.

처음에 연산자의 우선순위를 DFS를 이용해서 모든 조합을 만들어보려고 했으나
생각해보니 연산자의 종류가 3개밖에 안되기 때문에
모든 경우의 수는 6가지입니다.

그래서 저는 제가 직접 6가지 경우의 수를 만들어서
연산을 진행했습니다.

        list.add(makeMax('+','-','*',expression));
        list.add(makeMax('+','*','-',expression));
        list.add(makeMax('-','+','*',expression));
        list.add(makeMax('-','*','+',expression));
        list.add(makeMax('*','+','-',expression));
        list.add(makeMax('*','-','+',expression));

연산을 진행할 때는 Stack과 ArrayList를 이용했습니다.

그림으로 표현해 보았습니다.
위 방법으로 구현하였습니다.

풀이는 아래와 같습니다.

풀이

import java.util.*;

class Solution {
    public long solution(String expression) {
        
        ArrayList<Long> list = new ArrayList<>();
        
        
        // 우승자에게 상금 지급
        // 상금 지급 방식이 달라짐
        // 숫자들과 3가지의 연산문자 만으로 이루어진 연산 수식
        // 가장 큰 숫자를 제출
        // 자유롭게 우선순위 재정의 단 같은 순위의 연산자는 없다
        // 음수인 경우 절댓값으로 변환하여 제출
        // 제출한 수가 가장 큰 참가자가 우승자 -> 이 숫자가 우승 상금으로 지급
        
        // 참가자에게 주어진 연산 수식이 담긴 문자열: expression
        
        //1. 안에 있는 연산의 종류를 파악한다.
        //2. 계산을 한다.
        //3. 최댓값을 구한다.
        
      
        list.add(makeMax('+','-','*',expression));
        list.add(makeMax('+','*','-',expression));
        list.add(makeMax('-','+','*',expression));
        list.add(makeMax('-','*','+',expression));
        list.add(makeMax('*','+','-',expression));
        list.add(makeMax('*','-','+',expression));
        
        
     
        Collections.sort(list);
        
        return list.get(list.size()-1);
    }

    
    static long makeMax(char one, char two, char three, String expression){
        
        char[] prior = {one,two,three};
        
        Stack<Long> st = new Stack<>();
        
        String operator = expression.replaceAll("[0-9]","");
        char[] opt = operator.toCharArray();
        
        //부호
        ArrayList<Character> optList = new ArrayList<>();
        for(char o : opt) optList.add(o);
        
        //숫자
        String[] v = expression.split("-|\\+|\\*");
        ArrayList<Long> numList = new ArrayList<>();
        for(String vv : v) numList.add(Long.parseLong(vv));
       
      

       
        
        for(int i=0;i<prior.length;i++) {
            if(!optList.contains(prior[i])) continue;
            //초기화
            st.add(numList.get(0));
            
            for(int j=0;j<optList.size();j++){
                if(prior[i]==optList.get(j)){
                    switch (prior[i]) {
                        case '+':
                        st.add(st.pop()+numList.get(j+1));
                        break;
                        case '-':
                        st.add(st.pop()-numList.get(j+1));
                        break;
                        default :
                        st.add(st.pop()*numList.get(j+1));
                    }
                } else st.add(numList.get(j+1));         
            }//for j
            char t =  prior[i];
            optList.removeIf(item -> item == t);
            numList = new ArrayList<>();
            int size =st.size();
            for(int j=0;j<size;j++){
                numList.add(st.pop());   
            }
            Collections.reverse(numList); 
          }//for i
          
        
        
        return Math.abs(numList.get(0));
        //return 0;
    }
}