1 ★★★ [프로그래머스][JAVA] 수식 최대화 (순열)

220605 

시간복잡도가 초과했었는데

기본으로 주어지는 연산자 3개 +,*,- 만으로

조합을 구성해야하는데 

문제의 예시의 ex)100-234+234243-345*... 등의 연산자 n개의 배열을 활용하여

조합을 구성했음(실수한 부분)

 

 

 

 

 

1. 주어진 String인 expression을 parsing하여 numList와 signList를 구하기

2. numList.size()값은 signList.size()보다 1크다

3. + - *의 순열을 구한 후에 answer의 후보값을 구하는 식을 짠다.

4. 원본 numList와 signList가 훼손되지 않게 (remove를 사용할 것이므로) 다른 list객체에 값을 복사한다.

 

 

import java.util.*;

class Solution {
    
    private static char[] sign = new char[]{'+', '-', '*'};
    private static boolean[] visited = new boolean[3];
    private static long answer;
    
    public long solution(String expression) {      
        answer = 0;
        calMostAbsValue(expression);
        return answer;
    }
    
    private void calMostAbsValue(String expression){
        List<Long> numList = new LinkedList<>();
        List<Character> signList = new LinkedList<>();
        
        Long num = -1L;
        for(int i=0; i<expression.length(); i++){
            char currChar = expression.charAt(i);
            if(currChar=='+' ||
                currChar=='-' ||
                currChar=='*'){
                numList.add(num);
                signList.add(currChar);
                num = -1L;
            }
            else{
                num = (num== -1L)? currChar-'0' : (num*10)+(currChar-'0');
            }
        }
        // flush
        numList.add(num);
        
        // numList.forEach(System.out::println);
        // signList.forEach(System.out::println);
        
        permutation(numList, signList, 0, new char[3]);
        
        
       
    }
    
    private void permutation(List<Long> numList, List<Character> signList,int stage, char[] signOrder){
        if(stage==3){
            List<Long> tempNumList = new LinkedList<>(numList);
            List<Character> tempSignList = new LinkedList<>(signList);
            // tempSignList.forEach(System.out::println);
            
            
            for(int i=0; i<signOrder.length; i++){
                for(int j=0; j<tempSignList.size(); j++){
                    if(tempSignList.get(j)==signOrder[i]){
                        long temp = calculate(tempNumList.get(j), tempNumList.get(j+1), tempSignList.get(j));
                        tempNumList.set(j, temp);
                        tempNumList.remove(j+1);
                        tempSignList.remove(j);
                        j--;
                    }
                }
            }
            // tempNumList.forEach(System.out::println);
            // System.out.println(tempNumList.get(0));
            answer = Math.max(answer, Math.abs(tempNumList.get(0)));

        }
        
        for(int i=0; i<3; i++){
            if(!visited[i]){
                visited[i] = true;
                signOrder[stage] = sign[i];
                
                permutation(numList, signList, stage+1, signOrder);
                visited[i] = false;
                
            }
            
        }
        
    }
    
    private long calculate(long a, long b, char sign){
        switch(sign){
            case '+':
                return a+b;
            case '-':
                return a-b;
            case '*':
                return a*b;
        }
        return 0;
    }
}